Python 高效检查大字符串是否包含子串的方法

Question

Python 不是我最擅长的语言，所以我在找到一些问题的高效解决方案时并不是特别在行。我有一个非常大的字符串（来自一个 30 MB 的文件），我需要检查这个文件里是否包含一个较小的子字符串（这个字符串只有几十个字符）。我现在的做法是：

if small_string in large_string:
    # logic here

但是这样做似乎效率很低，因为它会检查文件中所有可能的字符组合。我知道只有在换行符上才会有完全匹配，那这样是不是更好先把文件读成一个列表，然后逐个对比这个列表里的内容呢？

补充说明：为了澄清“仅在换行符上匹配”的意思，这里有个例子：

small_string = "This is a line"
big_string = "This is a line\nThis is another line\nThis is yet another"

如果我没记错的话，使用 in 这个关键词会检查所有的字符序列，而不仅仅是每一行。

Answer 1

什么叫太慢呢？我刚刚在一个170MB的字符串末尾测试了一个独特的字符串，结果在我按下回车键的瞬间，它就完成了。

Answer 2

真的慢吗？你提到的是30MB的字符串，我们来试试更大的字符串：

In [12]: string="agu82934u"*50*1024*1024+"string to be found"

In [13]: len(string)
Out[13]: 471859218

In [14]: %timeit "string to be found" in string
1 loops, best of 3: 335 ms per loop

In [15]: %timeit "string not to be found" in string
1 loops, best of 3: 200 ms per loop

我觉得335毫秒在450MB的字符串中查找子字符串并不算太久。

Answer 3

你可以使用以下这些算法：

• Rabin-Karp 字符串搜索算法

• Knuth-Morris-Pratt 算法（简称 KMP），你可以在这里查看实现 这里

虽然我觉得 KMP 算法更高效，但它的实现比较复杂。第一个链接里有一些伪代码，应该能让你在 Python 中很容易实现。

你可以在这里寻找其他替代方案：http://en.wikipedia.org/wiki/String_searching_algorithm