💻村长云服务器 IV：当暴力美学遇上AC自动机！

村长抱着那台熟悉的二手服务器冲进院子，机箱上的标签从’村长云服务器·公测版’ 又升级成了’‘村长云服务器·旗舰版’’——手写字歪歪扭扭，一看就是老头自己拿马克笔描的。风扇还是那个风扇，嗡嗡声堪比直升机，升了版本号没升硬件，典型的“软件升级，硬件抗压”。

“小白！老板娘说抽奖系统现在流量暴涨，用户发的弹幕里老有人刷敏感词！什么’代抽’、‘外挂’、‘假一赔十’——把评论区搞得乌烟瘴气！”村长把显示器往桌上一搁，屏幕上滚动着一条超长弹幕文本，旁边密密麻麻列着一百多个敏感词，从"代抽"到"假货"，从"退款"到"差评"，琳琅满目，活像一本黑话词典。

“老板娘要我上线一个‘敏感词拦截系统’，统计文本里到底命中了多少个敏感词！” 村长咽了口唾沫：“她还说了，如果今天搞不定，就把我的服务器拿去垫桌角！”

我瞥了眼数据范围：word 长度 100，patterns 数量 100，每个模式串长度不超过 100——这任务倒是不难。

暴力一行流

“这不就是找子串吗？”我嘴角一勾，“Python 里有 in 运算符，一行流搞定！看我的 Pythonic 大法——”

def numOfStrings(patterns: List[str], word: str) -> int:
	return sum(p in word for p in patterns)

一气呵成。我得意地晃了晃鼠标，“这就叫站在巨人的肩膀上——哦不，是站在 CPython 的肩膀上！in 运算符底层调用的是 C 实现的字符串查找算法，常数小、效率高，对于这种小规模数据绰绰有余。人生苦短，我用 Python，能一行解决的事，绝不多写第二行！”

话音未落，后脑勺"啪"地挨了轻轻一下——“一行流能 AC，是因为评测机今天心情好，数据没上强度。”

老勇者不知何时已站在我身后，手眼神锐利如刀：“如果 patterns 有十万个，word 长度百万，你这 in 每次都要从头扫描 word。数据量一上去，CPython 的肩膀也扛不住。”

我愣了一下：“呃……十万个模式串？百万长度的文本？老板娘的抽奖系统怎么可能会有这么大流量？”

老勇者微微一笑：“年轻人，格局打开。你现在做的小题，是未来大战的预演。听说过多模式匹配吗？那可是搜索引擎、病毒扫描、内容审核系统的核心武器。今天好好学一招，将来遇到千万级数据就不至于被按在地上摩擦。”

多模式匹配

“小子，听好了。”老勇者从我的本子上撕了张纸，拿起笔就开始画，“在一个文本串中同时查找多个模式串——这叫多模式匹配问题（Multi-Pattern Matching）。对于这种问题，有几把经典武器。”

“第一把，暴力遍历。”他指了指屏幕上的 in 操作符，“就是你刚才那行代码。每个模式串独立扫描 word，相当于派一百个侦探，每个人都要把整栋楼从头搜到尾。数据小的时候确实能用，数据一大，就是百人团灭现场。O(m × n)，不解释。”

“第二把，KMP 单模式优化。”他在纸上画了一排箭头，“预处理模式串，构建一个部分匹配表，在失配时跳过已经匹配过的前缀，避免重复比较。相当于每个侦探都带着一张‘搜过的地方不用再搜’的线索图。但问题是——你还是要派一百个侦探分别搜一遍楼——KMP 只优化了单个侦探的效率，没减少侦探的数量。有 m 个模式串，就要跑 m 次 KMP。”

“第三把：Trie 树（字典树）。”老勇者在纸上又画了一棵树，节点上标满了字母，“把所有模式串插进一棵树里，共享前缀。比如 ‘abc’ 和 ‘abd’，它们的前缀 ‘ab’ 可以共用，走到分叉路口再各走各的。空间换时间。”

他停顿了一下，用笔重重一点：“但 Trie 有个致命缺陷：当你在某个节点失配时，必须回到根节点重新开始。 比如你匹配了 ‘abcde’，下一个字符不是 ‘f’，你就得从根节点的 ‘a’ 重新来。文本串的指针要回溯，最坏情况依然是 O(n × m)。相当于侦探走到死胡同，必须跑回大楼入口重新找路。纯 Trie 没有记忆，不会跳跃，只能硬着头皮回溯。”

他扫了我一眼，确认我跟上了节奏，然后在纸的正中央写下四个大字，字迹遒劲有力：

“第四把：AC 自动机（Aho-Corasick Automaton）。”

“多模式匹配的终极武器。”老勇者的声音低沉而充满力量，“ Trie 树 + KMP 失败指针思想的融合体——Trie 负责存储所有模式串，KMP 的失配思想负责处理失配时的跳转。所有模式串构建成一棵 Trie，然后加上两个指针——fail 和 last——让文本串在自动机上只跑一趟，就能同时匹配所有模式串。”

他在 Trie 树上画了一堆虚线箭头：“核心在于两个指针：fail 指针（失配指针） 和 last 指针（后缀链接）！”

Fail 指针：失配时的传送门

“核心一：fail 指针。fail 指针指向的是’当前字符串的最长真后缀’，且这个后缀也是某个模式串的前缀。” 老勇者指了指图上的节点，“当你在当前节点失配（下一个字符不匹配）时，就跳到 fail 指向的节点继续尝试匹配，不需要回到根节点重新开始！”

他顿了顿：“比如你匹配了 ‘abcd’，失配了，fail 指针可能指向 ‘bcd’、‘cd’ 或 ’d’ 对应的节点——具体是哪个，取决于哪个后缀同时也是某个模式串的前缀。”

“这和 KMP 的 next 数组异曲同工，但它是跨模式串的——KMP 只在单个模式串内部跳转，AC 自动机的 fail 可以在不同模式串之间跳跃。相当于侦探在迷宫里走到死胡同，不是传送回城，而是通过密道直接跳到另一条分支上。文本串的指针永不回溯——这是 AC 自动机的灵魂。”

Last 指针：直达模式串末尾的捷径

“核心二：last 指针。”他继续画箭头，“ fail 指针有个小问题：它跳到的节点，不一定是某个模式串的末尾。 比如你匹配到 ‘abcde’，fail 指针可能跳到 ‘cde’，但 ‘cde’ 可能只是个中间节点，不是完整的模式串。如果只靠 fail，你还得继续沿着 fail 链一层一层往上跳，直到找到某个模式串的末尾，或者跳回根节点。”

“这时候就需要 last 指针了——后缀链接，直接指向 fail 链上第一个是模式串末尾的节点。如果整条 fail 链上都没有模式串末尾，last 就指向根节点。它相当于 fail 链上的‘直达电梯’——不用一层一层爬楼梯，直接按顶层按钮就到了。”

他笔锋一转：“回到刚才的例子。你站在 ‘abcde’ 节点，想收集所有以当前位置结尾的模式串。先检查自己：如果是模式串末尾，记下来。然后沿着 last 指针一跳，直接飞到 fail 链上下一个模式串末尾（比如 ‘cde’ 如果恰好是某个模式串，last 就指向它）。再检查，再跳，直到跳到根节点为止。整个过程，你只访问了模式串末尾节点，中间那些不是末尾的节点全被跳过了。这就是 O(1) 均摊时间的秘密——每收集一个命中才走一步，零命中零步，十个命中十步。比沿着 fail 链一个一个节点傻找，效率高了一个数量级。”

老勇者放下笔，总结道：“AC 自动机的生命周期分三步。第一步，构建 Trie，把所有模式串插进去。第二步，构建 fail 和 last 指针，BFS 一遍搞定。第三步，查询文本串，逐个读入字符，在自动机上转移状态——失配时靠 fail 跳转，命中时靠 last 收集。时间复杂度 O(n + m + z)，n 是文本长，m 是所有模式串总长，z 是匹配次数。”

他盯着我，一字一顿地说：“看到没？跟模式串数量无关。 相当于只派一个侦探，但他脑子里装着所有敏感词的线索地图，还有传送门（fail）和快捷通道（last），搜一遍楼就把所有敏感词全揪出来。”

我听得头皮发麻：“把暴力匹配的重复劳动，通过预处理转化成智能跳转？”

“没错！”老勇者眼中闪过一丝赞许，“AC 自动机的思想非常优雅——它把多模式匹配问题转化成了确定有限状态机（DFA）的问题。你每读入一个字符，就在状态机里转移一次，瞬间就能知道当前匹配到了哪些模式串。这就像玩游戏时开了全图挂+自动寻路，一眼就能看到所有敌人的位置，还能自动规划最优路径。”

我感觉灵光一闪：“AC 自动机就是把 Trie 树上的匹配路径编码成了状态，fail 指针就是失配时的状态转移！”

“悟性不错。”老勇者难得地点点头，“那现在，想不想亲手实现一把这个’全图挂’？”

我摩拳擦掌：“当然！给我代码模板，我要开始抄——哦不，是开始学习了！”

AC 自动机

第一步：定义 Trie 树节点

首先，Trie 树的每个节点代表一个字符，从根节点到某个节点的路径就是一个字符串。需要四个字段：son 数组存储 26 个字母的子节点，fail 是失配跳转指针，last 是直达下一个模式串末尾的后缀链接，cnt 用来记录这个节点是多少个模式串的结尾。"

class Node:
    __slots__ = 'son', 'fail', 'last', 'cnt'
    
    def __init__(self):
        self.son = [None] * 26  # 26个小写字母的子节点（a-z对应索引0-25）
        self.fail = None         # 失配指针：当前字符不匹配时跳到哪里
        self.last = None         # 后缀链接：快速跳到下一个一定是模式串末尾的节点
        self.cnt = 0             # 该节点是多少个模式串的末尾（计数器）

第二步：构建 AC 自动机

接下来，把所有模式串插入 Trie 树。这部分和普通字典树一模一样——遍历每个字符，沿着 son 往下走，没有子节点就新建，走到末尾时 cnt++，表示这里是一个模式串的终点。

class AhoCorasick:
    def __init__(self):
        self.root = Node()
    
    def put(self, pattern: str) -> None:
        cur = self.root
        for ch in pattern:
            i = ord(ch) - ord('a')  # 字符转索引
            if cur.son[i] is None:
                cur.son[i] = Node()  # 没有这个子节点就创建
            cur = cur.son[i]
        cur.cnt += 1  # 标记这是一个模式串的末尾

“注意看”，老勇者提醒道，“cnt 是累加的。如果 patterns 里有三个 “a”，那么表示 “a” 的那个节点的 cnt 就是 3。这样在查询时，我们一次性就能知道有多少个相同的模式串在这里匹配。”

第三步：构建 fail 和 last 指针（BFS）

“重头戏来了——构建 fail 和 last 指针。这是 AC 自动机的灵魂所在。”老勇者搓了搓手，仿佛在展示什么绝世武功，“用 BFS（广度优先搜索）逐层处理整棵 Trie 树。”

初始化部分：根节点的 fail 和 last 都指向自己，因为根节点没有父节点，失配了也只能回到自己。然后遍历根节点的每个子节点：如果 son[i] 为空，就让它直接指向根节点，形成自循环——这样匹配时遇到不存在的字符能自动回到起点；如果 son[i] 存在，它的 fail 和 last 都指向根节点（第一层节点的 fail 只能是根），然后入队等待后续处理。

def build_fail(self) -> None:
    self.root.fail = self.root.last = self.root  # 根节点的 fail 和 last 都指向自己
    
    q = deque()  # BFS 队列    
    # 初始化第一层节点（根的直接子节点）
    for i, son in enumerate(self.root.son):
        if son is None:            
            self.root.son[i] = self.root	# 虚拟子节点：直接指向根节点，方便后续失配时跳转
            continue
        son.fail = son.last = self.root		# 第一层的 fail 和 last 都指向根
        q.append(son)  						# 入队，后续处理它的子节点
    
    # BFS 遍历整棵树，逐层构建 fail 和 last 指针
    while q:
        cur = q.popleft()  # 取出队首节点
        for i, son in enumerate(cur.son):  # 遍历当前节点的26个子节点
            if son is None:
                # 路径压缩：空子节点直接指向 cur.fail 的对应子节点
                # 这样匹配时遇到不存在的字符，一步就能跳到下一个可能匹配的位置
                cur.son[i] = cur.fail.son[i]
                continue
            
            # 计算 son 节点的 fail 指针：沿着父节点的 fail 链找
            # cur.fail.son[i] 就是"以 cur 的最长可匹配后缀为前缀，且下一个字符也是 ch 的节点"
            son.fail = cur.fail.son[i]
            
            # 计算 son 节点的 last 指针：直达下一个一定是模式串末尾的节点
            # 如果 fail 节点本身就是某个模式串的末尾（cnt > 0），last 就指向 fail
            # 否则指向 fail.last，继续沿着后缀链接往上找
            son.last = son.fail if son.fail.cnt else son.fail.last
            
            q.append(son)  # 处理完当前节点，把它加入队列，后续处理它的子节点

我挠挠头，指着那行 cur.son[i] = cur.fail.son[i] 问：“等等，这里为什么要修改 son 数组？这不是把原来的 Trie 树结构改了吗？”

“这就是路径压缩的精髓！”老勇者眼睛一亮，“原本如果 son[i] 为空，匹配时你得手动沿着 fail 链一层层往上找，直到找到某个节点有 son[i]。现在直接把空子节点指向 cur.fail.son[i]，匹配时不管 son[i] 存不存在，直接 cur = cur.son[i] 跳过去就完事——要么是真正的子节点，匹配成功；要么是 fail 链上的后备节点，失配后跳转到下一个可能位置。省掉了中间跑路的时间，一步到位。”

第四步：查询文本串

最后是查询阶段。从根节点出发，遍历 word 的每个字符。因为路径压缩了，son[i] 总有值——要么是真正的子节点，要么是 fail 链上的后备节点——所以直接 cur = cur.son[i] 就行，全程不需要手动判断失配。每到一个新节点，沿着 last 链收集所有命中的模式串。

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        ac = AhoCorasick()
        for pattern in patterns:
            ac.put(pattern)		# 把所有模式串插入 AC 自动机
        ac.build_fail()			# 构建 fail 和 last 指针
        
        ord_a = ord('a')		
        cur = ac.root  			# 当前状态，从根节点开始
        ans = 0  				# 统计匹配的模式串数量
        
        # 遍历文本串的每个字符
        for ch in word:              
            cur = cur.son[ord(ch) - ord_a]		# 自动机转移，无需判空            
            match_node = cur
            while match_node.cnt >= 0:  		# cnt >= 0 表示这个节点还没被统计过
                ans += match_node.cnt  			# 累加这个节点是多少个模式串的末尾
                match_node.cnt = -1  			# 标记为已统计，避免重复计数
                match_node = match_node.last  	# 跳到下一个可能是模式串末尾的节点
        
        return ans

我盯着那个 while match_node.cnt >= 0 的循环问：“为什么要标记为 -1？这个循环是在干嘛？”

“避免重复统计同一个模式串。”老勇者解释道，“假设 patterns = ["a", "ab", "abc"]，word = "abc"。当匹配到 'c' 时，当前节点表示 "abc"，它本身是模式串末尾，cnt=1；它的 last 链可能指向 "ab" 对应的节点，也是模式串末尾；继续沿着 last 链走，可能还指向 "a" 对应的节点。需要沿着这条链把所有匹配的模式串全统计一遍。”

“但需要统计的是‘patterns 中有多少个字符串是 word 的子串’，而不是‘总共匹配了多少次’。如果 word 后面又出现了一个 "abc"，你不能把 "abc" 再算一遍。所以第一次匹配到时，把 cnt 累加到答案，然后立刻标记为 -1——之后不管 word 里再出现多少次 "abc"，while 循环的条件 cnt >= 0 都不满足，直接跳过。这就叫‘见一次就标记，绝不重复计数’。”

“哦！”我恍然大悟，“last 链负责一次匹配中收集所有命中的模式串，cnt = -1 负责跨匹配去重——两条机制，一个管纵向深度，一个管横向广度，完美配合！”

“没错！”老勇者赞许地点点头，“这下你真懂了。”

尾声

提交，AC！这次不是靠 CPython 的肩膀，而是靠自动机的铁拳——文本串只扫一遍，跟模式串数量无关。

p in word 的暴力一行流，每次 in 都是独立的扫描，相当于给每个敏感词派一个侦探，让他们各自为战，每个人都要把整栋大楼从头到尾搜一遍；而 AC 自动机，则是把所有的扫描合并成了一次遍历——只派一个侦探，但他脑子里装着所有敏感词的线索地图，脚下踩着传送门（fail 指针），手里拿着快捷通道（last 指针），搜一遍楼就能把所有敏感词连锅端！从 O(m × n) 到 O(n + m)，差距不是常数倍，是数量级的碾压。

“好！好！好！”村长看着运行结果，乐得合不拢嘴，一把抱住那台还在嗡嗡作响的二手机箱，“这下服务器保住了！我的‘村长云旗舰版’不用去垫桌角了！”

他激动地抹了把眼泪，但随即又凑到我身边，搓着手问道：“小白啊，真遇到大规模流量——比如老板娘的抽奖系统突然爆火，同时有十万个用户在线疯狂刷屏，老板娘要拦截十万个敏感词、处理百万字的文本……就用这个 AC 自动机，顶得住吗？”

我看着他那张写满担忧的脸，忍不住笑了：“村长，把心放回肚子里！AC 自动机的时间复杂度是 O(n + m + z)——跟模式串的数量完全无关！就算有一万个敏感词，也只是 Trie 树稍微大一点，查询的时候，文本串依然只需要从头到尾扫一遍！”

我瞅着屏幕上的AC自动机，掷地有声地说：“有了 AC 自动机，以后就算流量翻十倍、一百倍，你的服务器也照样扛得住！”

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。