代码之家 › 专栏 › 技术社区 › Kenneth Cochran

找到所有子字符串的最快方法是什么?

search algorithm

Kenneth Cochran · 技术社区 · 15 年前

这纯粹是出于好奇。我浏览了一篇比较各种字符串搜索算法的文章,发现它们都是为了找到第一个匹配的子字符串而设计的。这让我想。。。如果我想找到子字符串的所有匹配项呢?

我相信我可以创建一个循环,使用KMP或BM的变体,并将每个发现的事件转储到一个数组中,但这似乎不是最快的。

分而治之的算法不是更好吗?

例如,假设您在字符串“abbcacabbccabcabc”中查找序列“abc”。

在第一步中,找到第一个字符的所有匹配项并存储它们的位置。
在每一个额外的过程中,使用前一个过程中的位置来查找下一个字符的所有匹配项,从而在每次迭代中减少下一个过程的候选项。

考虑到我提出这个想法的难易程度,我认为30年前已经有人提出并改进了它。

4 回复 | 直到 15 年前

Nick Dandoulakis 15 年前

看见 Suffix array

应用

字符串的后缀数组可以是用作快速定位的索引子字符串在绳子。发现每一件事子字符串的查找以子串。多亏了词典排序,这些后缀将按顺序分组后缀数组,可以找到有效地进行二进制搜索。如果直接实施,这二进制搜索需要O(mlogn)时间, 式中,m是长度子串。避免重做比较,额外的数据结构提供最长的后缀的常用前缀(LCP)是构造,给出O(m+logn)搜索时间

Martin Hock 15 年前

如果只处理给定字符串一次,那么后缀数组就太过分了。创建需要O(n logn)时间,因此KMP风格的算法将击败它。此外,如果字符串很大,或者希望在收到字符串时实时获得结果,那么后缀数组将不起作用。

当然,除了用于存储匹配的内存(如果您只是打印匹配或在进行过程中处理匹配,这也可能是不必要的)之外,还可以修改KMP算法,以便在找到匹配后继续运行,而不占用额外的内存。首先,以 Wikipedia implementation 并将“return m”语句修改为“将m添加到索引列表”。但你还没做完。你还需要问自己,你是否允许重复出现?例如,如果您的子字符串是“abab”,并且您正在查看主字符串“abababab”,那么会出现两次还是三次?在我给出的示例中(“作为一个开始”),您可以将I重置为0以给出“2”的答案,或者您可以在“add m”之后使用“否则”的情况给出“3”的答案。

Foxfire 15 年前

没有单一的“最快方式” 这取决于

A) 字符串的实际构造(长度、字符分布等)

B) 它在哪个硬件上运行

C) 如果你想让所有结果并行或连续

D) 其他参数(例如,可以找到重叠的元素,是否搜索一次或多次)

E) 如果你认为这个实现是特定的,或者只是学术性的。在实现过程中,还有很多其他方法可以优化内容。临时存储(就像你建议的那样)通常非常昂贵。

你的想法,例如,将完全垃圾长字符串的任何CPU缓存。因此,在这些情况下,速度会非常缓慢。

MAK 15 年前

KMP和BM也可以轻松地用于查找多个匹配项。我还建议使用 Rabin-Karp ,IMHO更容易理解,但对于多个匹配(O(n+k*m)我想,其中n是文本的长度,m是模式的长度,k是出现的次数)来说,速度并没有那么快。但对于重叠匹配和非重叠匹配都很容易修改。

它也可以使用后缀树/后缀数组来实现,但它们更难编码,也不能真正提高速度。