Python中如何高效实现字符串搜索功能？
有一个长度为 50 万的字符串列表，现在要查找某个字符串是不是这些字符串的字串，找到所有符合的字符串. 我用 python 遍历实现了一遍，性能不太满足，各位有没有什么建议？
Python中如何高效实现字符串搜索功能？
17 回复
用Python做字符串搜索，最直接的就是in操作符或者str.find()，但效率要看场景。
简单场景：in操作符最快最直观。
text = "这是一个示例文本"
if "示例" in text:
print("找到了")
需要位置信息：用str.find()或str.index()。
pos = text.find("示例")
if pos != -1:
print(f"在位置 {pos} 找到")
复杂模式匹配：上正则表达式re模块。
import re
pattern = r"\d+" # 匹配数字
match = re.search(pattern, "abc123def")
if match:
print(f"找到数字: {match.group()}")
大量固定关键词：考虑Aho-Corasick算法（比如ahocorasick库），预处理后搜索是O(n)复杂度。
# 示例安装：pip install pyahocorasick
import ahocorasick
A = ahocorasick.Automaton()
for keyword in ["苹果", "香蕉", "橙子"]:
A.add_word(keyword, keyword)
A.make_automaton()
for end_index, found in A.iter("我喜欢苹果和香蕉"):
print(f"在位置{end_index}找到: {found}")
总结：根据需求选方法，简单用in，复杂用re，大量关键词用自动机。
字串 => 子串？
首先选择一个不出现在任何字符串里的一个字符 c，例如 c 选择 \0，然后把所有字符串接在一起 S = s1 \0 s2 \0 … \0 sn，接着制作 S 的后缀树（线性时间），然后就可以很容易做你需要的事情了。
具体实现上，你不需要真的构造出 S 这个字符串，在制作后缀树的过程中可以 virtually 表示它。
不放设列表里有 n 个字符串，每个串长为 m。不管怎么做，第一次匹配都逃不了 O(nm)的时间复杂度。
如果你就匹配一次，直接用 KMP 挨个匹配就好，O(nm)。
如果你有多个模式串，要匹配多次，建议先把 n 个文本串建成一颗 Trie 树，建树的时间是 O(nm)，以后每次匹配的时间只需要 O(m)。
