后缀自动机（SAM）不能直接用于多模式匹配，因其本质是单串所有子串的状态机，转移边仅对原串子串有效；若拼接多模式建SAM，会引入跨分隔符的非法子串、endpos失真、匹配归属难判定等问题，导致实现复杂且失去O(m)查询优势。
后缀自动机（SAM）本身不直接支持多模式匹配；它适合单串的子串查询，要处理多个模式，得配合 Aho-Corasick 或把所有模式拼接建 SAM 再加 endpos 标记——但后者容易漏匹配、难维护，实际项目中不推荐。
为什么不能直接用单个 SAM 做多模式匹配？
后缀自动机本质是原串所有子串的状态机，它的转移边只对「原串的子串」有效。如果你把多个模式拼成一个长串（如 "pat1#pat2#pat3"），虽然能建出 SAM，但：
-
endpos集合不再对应原始模式的出现位置，跨#的路径会引入非法子串（比如"t1#pa"） - 无法区分哪个匹配属于哪个模式，除非额外记录每个状态覆盖了哪些模式，实现复杂度陡增
- 查询时需遍历所有终止状态并回溯路径，时间不可控，失去 SAM 的
O(m)查询优势
更稳妥的做法：用 Aho-Corasick 替代 SAM 处理多模式
多模式匹配的工业级解法就是 Aho-Corasick 自动机，它专为该场景设计，Python 有成熟封装：
推荐使用 ahocorasick 库（pip install ahocorasick）：
立即学习“Python免费学习笔记（深入）”；
python-script-generator
下载
快速生成专业的 Python 脚本和应用代码。一键创建完整项目结构，支持CLI、API、爬虫、Bot、Django等多种项目类型，包含完整的项目结构、配置文件、依赖管理、测试、README和文档。
import ahocorasick
<h1>构建 AC 自动机</h1><p>ac = ahocorasick.Automaton()
patterns = ["he", "she", "his", "hers"]
for idx, pattern in enumerate(patterns):
ac.add_word(pattern, (idx, pattern))</p><p>ac.make_automaton()</p><h1>查询</h1><p>text = "ushers"
for end_idx, (pattern_idx, pattern) in ac.iter(text):
start_idx = end_idx - len(pattern) + 1
print(f"match '{pattern}' at [{start_idx}:{end_idx+1}]")
注意点：
-
ac.add_word()中 value 可存任意标识，建议用元组记录原始 pattern 和 ID，避免歧义 - 调用
ac.make_automaton()必须在所有add_word()后，否则失效 - 返回的
end_idx是匹配结束位置（0-based），需手动算起始位置
如果坚持用 SAM：只能用于「单文本 + 多查询模式」场景
即：有一个很长的主串 S，你要反复检查多个模式 P1, P2, ..., Pk 是否为其子串（不要求定位或计数）。这时可以对 S 建 SAM，每个 Pi 单独走转移：
def match_in_sam(sam, pattern):
node = 0 # root
for c in pattern:
if c not in sam[node]['trans']:
return False
node = sam[node]['trans'][c]
return True
<h1>假设 sam 已通过标准方式构建（dict of dict）</h1><h1>每次查询 O(len(pattern))，无额外空间开销</h1><p>关键限制：
- 仅判断存在性，不返回位置、不支持通配符、不支持重叠统计
- SAM 构建复杂（约 40 行核心代码），易写错
clone和link逻辑 - 若模式数量极大（如 >10⁵），不如预处理成 AC 自动机一次构建多次查询
真正需要 SAM 的场景，其实是子串相关统计（如不同子串数、最短/最长未出现子串、两个串的最长公共子串），而不是“给一堆词找它们在文本里有没有”。多模式匹配这件事，别跟 SAM 较劲。
