我有一个自定义迭代器(准确地说是 TokenIterator，它迭代标记化的 php 代码)。项目是简单的对象(添加了一些规范化方法的“属性包”)
我必须实现搜索功能，如果 1. 一个迭代器包含另一个或 2. 两个(或更多)迭代器重叠(有一些参数化)。
目前我使用天真的方法来 (1) - O(NxM) 双循环搜索，并且 (2) 尚未实现。
在开始重新实现真正智能的字符串搜索算法之前，我想知道是否存在一些有效的实现？也许某些深埋在某些框架或通用库中以供重用的东西？哪种算法最适合这里？
最佳答案
首先想到的是您在谈论集合操作，迭代器可以说不是最佳解决方案。
我不知道您的问题是否有任何现有解决方案，但作为一般解决方案，我会使用哈希表。例如，使用第一个集合的标记构造一个哈希表(我从现在起将其称为集合，因为我觉得 Iterator 不是最好的词)，你可以在 Theta(N) 中完成，然后尝试将另一个集合插入同一个哈希表中。第一次发生碰撞时，您会知道存在重叠。当然，如果散列空间很宽并且散列函数保证冲突量可以忽略不计，那么这种方法效果很好，但是总是可以编写某种变通方法。
鉴于 PHP 具有关联数组(这是哈希表的一种形式)，您还可以创建一个以标记作为键的数组，这同样可以在 Theta(N) 中完成，然后使用 array_key_exists。 array_key_exists 绝对有可能只不过是对键列表的线性扫描，因为我不熟悉 PHP 的内部结构，但我非常有信心，如果将关联数组实现为哈希表，它应该实现得更多效率高于线性扫描。
关于php - 有效搜索 php 迭代器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4525235/