哪个数据结构和/或算法适合这个问题？

Question

我有一个30MB.txt文件，其中包含如下随机字符串：

416
abcd23
cd542
banana
bambam

每行有1个单词，单词之间用新行隔开

我需要在文件中搜索我选择的子字符串并返回文件中所有匹配的字符串。更清楚地说：

Input: cd

Output: abcd23, cd542

广义后缀树、后缀树或后缀数组是否适合这类问题，或者是否有更快的方法？（时间复杂性很重要）

另外，我的编程技巧有点粗略，所以任何一种例子都会很感激

Answer 1

假设您正在文件中找到包含一个字符串的字符串，那么最快的方法就是遍历该文件，并在每一行上检查字符串函数'in'或'find'，如下所示。你知道吗

def find_matches(filename, txt):
     with open(filename, 'r') as f:
         return [line for line in f if txt in line] # using 'in'

用法示例：

matches = find_matches('myfile.txt', 'cd')

简单地读取文件可以避免构造其他方法（如读取文件）的字段的开销。另外：What is the fastest way to search a CSV file。你知道吗

in或find中使用的字符串方法基本上依赖于用C实现的优化fastsearch，其每字符串搜索的效率为：

It looks like the implementation is in worst case O(N*M) (The same as a naive approach), but can do O(N/M) in some cases (where N and M are the lengths of the string and substring respectively), and O(N) in frequent cases