java - 我们如何在O(n)时间下实现 "substring-match"？

我的作业需要读取大量随机输入的文件，例如:

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)的性能更好？

最佳答案

您可以看看Boyer-Moore string search algorithm或Knuth-Morris-Pratt string search algorithm。它们具有良好的渐近性能，但是我不知道不需要至少读取一次(几乎所有)输入和输出字符串一次的算法，因此比O(n)性能要好(其中n是输入的大小)。

关于java - 我们如何在O(n)时间下实现 "substring-match"？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8164540/