我们如何在O(n)时间内实现“子字符串匹配”？

Question

我有一个作业需要读取一个包含大量随机输入的文件，例如：

Adana 
Izmir Adnan Menderes Apt
Addis Ababa
Aden
ADIYAMAN
ALDAN
Amman Marka Intl Airport
Adak Island
Adelaide Airport
ANURADHAPURA
Kodiak Apt
DALLAS/ADDISON
Ardabil 
ANDREWS AFB
etc..

如果我指定搜索术语，程序应该找到包含子字符串的行。例如，如果搜索术语为“uradha”，则程序应显示ANURADHAPURA。如果搜索术语为“airport”，则程序应显示Amman Marka Intl Airport, Adelaide Airport。 任务规范中的引用：“您需要考虑效率编写此应用程序，就好像涉及大量数据和处理一样…” 我可以很容易地使用循环实现此功能，但性能将为O（n）。我想使用trie，但似乎仅在子字符串从索引0开始时才起作用。 我想知道是否有比O（n）更好的性能解决方案？

- Pacerier

---

所有的行都像所示的那样短吗？ - Michael J. Barber

@MichaelJ.Barber。基本上需求比较模糊，我只提供了一个示例文件：http://qweop.com/test/airports.dat - Pacerier

你需要量子计算机才能在O(n)的时间复杂度下遍历N个项目吗？ - Denis Tulskiy

@DenisTulskiy 你是什么意思？ - Pacerier

@Pacerier：如果你有一个长度为n的输入字符串，你至少要遍历每一个字符一次。如果没有量子计算机，你无法比O(n)更快地完成它。 - Denis Tulskiy

对于单个查询，无法达到O(n)以下的时间复杂度，但如果您有多个查询，则可以通过仅在O(n)时间内构建后缀树或后缀数组来获得大幅加速，然后使用它来解决每个查询，时间与查询长度成比例。 - j_random_hacker

Answer 1

这是一个最坏情况下时间复杂度为O(n)的算法。

顺便说一句，你应该把这个链接添加到书签：http://www-igm.univ-mlv.fr/~lecroq/string/

- nullpotent

Answer 2

你可以看看Boyer-Moore字符串搜索算法或Knuth-Morris-Pratt字符串搜索算法。它们的渐进性能很好，但我不知道是否存在一种算法，它不需要至少读取一次（几乎全部）输入和输出字符串，并且因此具有比O（n）更好的性能（其中n是输入的大小）。

- Sylvain Defresne

---

对于已知较短的子字符串，Rabin-Karp算法也是一个选择。 - rossum

Answer 3

我的直觉告诉我你考虑使用字典树是正确的，你可能需要查看维基百科上关于字典树页面的这一部分（链接），该页面链接到后缀树以获取更多想法。不幸的是，这些想法的时间复杂度为O(n)。

- David Wheaton

Answer 4

如果输入文本几乎是静态内容（或值并不经常添加，并且新增的值都在输入源的末尾），但搜索很频繁，您可以尝试以下方法（可能与trie相同）：

1）读取整个文本（也要在添加新元素时更新），并准备索引表（将符号映射到匹配发生的坐标（行或带位置的行））。

'aa' - 1, 15, 27... 
'as' - 1, 15, 17...
'ba' - 2, 3, 15...
...

2) 先通过前两个符号在索引表中查找坐标。

3) 然后根据这些坐标在输入文本中继续搜索。

- Vitaliy

---

抱歉，我不太明白你的意思。这是否意味着我需要为所有可能的输入'a'到'zzzzzz'创建一个映射（这太大了，无法实际使用）？ - Pacerier

这被称为倒排索引。它可以非常快速，因为索引告诉您如何聚焦搜索。 - Michael J. Barber

@Pacerier：是的，索引表会很大，甚至比输入源还要大，但它将提高搜索性能。 - Vitaliy

@MichaelJ.Barber 嘿，很酷，但是假设我只有三个短输入“老虎”，“狮子”和“熊”，你的意思是我必须建立一个包含33行的表格（t，i，g，e，r，ti，ig，ge，er，tig，ige，ger，tige，iger，tiger，l，o，n，li，io，on，lio，ion，lion，b，e，a，be，ea，ar，bea，ear，bear）吗？ - Pacerier

因为我想知道这种方法的可扩展性如何。运行测试文件（http://qweop.com/test/airports.dat）给出了286318行... - Pacerier

不，这不是必需的。你只需要使用固定长度的序列，例如字符对。然后在所有包含 'ti'、'ig'、'ge' 和 'er' 的行中搜索“tiger”是必要的。我用类似的方法评估公司名称的相似度；它比比较所有名称对快一个数量级。索引键的适当长度取决于数据；就像进行真正任务一样做一些测试。 - Michael J. Barber

Answer 5

Boyer-Moore算法及其衍生算法可以实现“O(n/m)”（其中n是文本串的长度，m是模式串的长度）在某些模式串中取得最优性能，但这取决于对模式串非重复性的要求。对于任意大的m（例如，当m远大于字符集大小时），这是不可能满足的，即使最好的情况也更像是O(n/256)或者O(n)。然而，在现实世界的应用中，由于模式串往往很小且不会出现病态周期性，因此Boyer-Moore算法及其衍生算法仍然表现出色。

个人建议采用“双向”算法（glibc实现中带有类似Boyer-Moore的扩展），因为它具有保证的O(n)上限和恒定的工作空间。

- R.. GitHub STOP HELPING ICE