使用树结构快速检查字符串是否包含大列表中短字符串的方案咨询

架构老林

2026-9-28

问题背景

我有一个由短字符串（单词）组成的大列表，需要检查其中是否有任意元素出现在另一个目标字符串（句子）中，不需要区分实际单词边界、空格、标点符号等内容。

这是Python中的典型解决方案：

def contains_one_of(sentence, words):
    for word in words:
        if word in sentence:
            return word
    return None

我见过一些实现相同功能的Python单行写法，但从算法层面来看，我能找到的所有实现基本都是对所有元素逐一调用包含检测函数，我推测这类包含检测函数底层采用滑动窗口类的实现逻辑。
按照我的测算，这类方案的时间复杂度约为O(nmo)

n = 列表长度
m = 句子长度
o = 列表中单词的平均长度

我认为可以用树结构优化该算法，但没有找到这类算法的相关参考资料。我大致的构想是将单词数组构建为树，每个节点对应一个字母，其所有子节点对应单词的下一个字母。只要单词长度较短、前缀重合度较高，我认为这个方案的效率会更优。

我已经用Python实现了一个版本，但更希望使用底层借助C实现字符比对的第三方包来提升性能。如果您知道这个算法的名称或者对应的实现包，麻烦告知我。

以下是我的实现版本，我知道还有很多优化空间，也想确认我的思路是否正确：

sentence = "hello there cat, welcome home"
words = ["cat", "car", "cam", "arm", "ace", "arc"]

# build a dict tree per letter
def build_tree(patterns):
    root = dict()
    for p in patterns:
        r = root
        for i, c in enumerate(p):
            if c not in r:
                if i >= len(p) - 1: # last element
                    r[c] = p
                else: # any other element
                    r[c] = dict()
            r = r[c]
    return root
            
# Check if the substring starts with a path through the tree
def starts_with_tree(sub, tree):
    level = tree
    for c in sub:
        if c not in level: # nowhere left to go
            return None
        elif isinstance(level[c], str): # if we found a string we are at the end
            return level[c]
        else:
            level = level[c] # go deeper
            

# Check if s contains any path through the tree
def contains_which(s, root):
    for i in range(len(s)):
        sub = s[i:] # A substring missing the first i characters
        result = starts_with_tree(sub, root) 
        if result:
            return result
    return None
        

# build the tree
tree_root = build_tree(words)
print(tree_root)
# search within tree
found = contains_which(sentence, tree_root)
print("Found:", found)

解答

你的思路完全正确，你自己实现的这个树结构就是前缀树（Trie 树），专门用于高效处理多字符串匹配、前缀查询类的场景。
如果还要进一步优化查询效率，可以用基于前缀树升级的Aho-Corasick算法（简称AC自动机），它在查询时不需要对每个句子的起始位置单独遍历，时间复杂度可以降到O(m + k)，其中m是句子长度，k是匹配到的结果数量，比你现在的实现效率更高，非常适合大词表下的多模式匹配场景。
如果要找底层用C实现的高性能Python包，可以用pyahocorasick，这个包是AC自动机的工业级实现，性能远高于纯Python写的前缀树版本，使用也很简单。
另外你现有的纯Python实现有个小问题：如果存在一个单词是另一个单词的前缀的情况（比如词表里同时有cat和cater），你的逻辑会提前返回短的单词，不会匹配到更长的，如果你有匹配最长词的需求需要调整终止节点的判断逻辑。

内容的提问来源于stack exchange，提问作者M'Goops