我们如何在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.如果搜索词是"机场",则应该显示该程序Amman Marka Intl Airport, Adelaide Airport

从作业规范中引用:"你要对这个应用程序进行编程,同时考虑到效率,好像涉及大量的数据和处理......"

我可以使用循环轻松实现此功能,但性能将为O(n).我正在考虑使用trie,但它似乎只有在子串从索引0开始时才有效.

我想知道哪些解决方案的性能优于O(n)？

Answer 1

这是 O(n)作为最坏情况时间复杂度的一个.

顺便说一下,你应该给这个链接添加书签:http://www-igm.univ-mlv.fr/~lecroq/string/

Answer 2

您可以查看Boyer-Moore字符串搜索算法或Knuth-Morris-Pratt字符串搜索算法.它们具有良好的渐近性能,但我不知道一个算法不需要至少读取一次(几乎全部)输入和输出字符串,因此会比O(n)性能更好(其中n是输入的大小).