php - 如何将数组中的行与掩码数组匹配？

Question

我有这样的数组:

array('1224*', '543*', '321*' ...) 其中包含大约 17,00 个“掩码”或前缀。

我有第二个数组:

array('123456789', '123456788', '987654321' ....) 其中包含大约 250,000 个数字。

现在，我如何使用掩码/前缀数组有效地匹配第二个数组中的每个数字？

[编辑]

第一个数组只包含前缀，每个条目最后只有一个 *。

Answer 1

好吧，这是一个解决方案:

预备步骤:

1. 排序数组 1，切断 *。

搜索:

1. 对数组 2 中的每个数字做
   1. 在数组 1 中找到第一个和最后一个条目，其中第一个字符与 number 的字符匹配(二进制搜索)。
   2. 对第二个字符执行相同的操作，这次不是搜索整个数组，而是在 first 和 last 之间搜索(二进制搜索)。
   3. 对第 n 个字符重复 2，直到找到一个字符串。

这应该是 O(k*n*log(n)) 其中 n 是平均数字长度(以数字为单位)和 k 数字的数量。

---

基本上这是一维的 Radix tree ，为了获得最佳性能，您应该实现它，但这可能非常困难。