AC自动机匹配边界：重叠与不重叠模式串计数实战

1. 从一道题看AC自动机的匹配边界问题字符串匹配这件事入门的时候觉得KMP已经够用了等到题目里出现“多个模式串”“可重叠”“不可重叠”这些限定词才发现单模式匹配那套思路根本兜不住。ZOJ 3228 这道题我第一次遇到的时候卡了整整一个下午不是因为AC自动机不会写而是因为“重叠”和“不重叠”这两个条件在自动机上的处理方式完全不一样而题目偏偏把两种查询混在一起。这道题的核心需求很明确给一个文本串再给若干个模式串每个模式串附带一个标记标记为0表示统计该模式串在文本中所有出现位置允许重叠标记为1表示统计该模式串在文本中不重叠的出现次数。最后按输入顺序输出每个模式串对应的计数结果。听起来像是AC自动机的模板题加一点小变形但真正动手写的时候你会发现允许重叠的计数可以在匹配过程中直接累加而不重叠的计数必须记录上一次匹配的结束位置判断当前匹配的起始位置是否大于上一次的结束位置。这个逻辑放在AC自动机的fail树遍历框架里需要额外维护每个模式串节点的状态信息。适合谁来参考这篇内容如果你已经写过基础的AC自动机知道怎么建trie、怎么构建fail指针、怎么在文本串上跑匹配但遇到“同一模式串多次出现需要区分重叠与否”这类需求时没有清晰的思路那这篇东西应该能帮你把这块补上。如果你还没接触过AC自动机建议先去把基础的多模式匹配原理搞清楚再回来看重叠判定的细节否则容易在fail指针跳转那里卡住。我下面会从整体设计思路开始拆然后讲清楚重叠与不重叠在代码层面到底怎么区分接着给出完整的实操流程和参数细节最后整理几个我实际调试时踩过的坑。代码用C写因为这类题目在竞赛场景下C的常数优势明显而且AC自动机的数组实现用C写起来更直观。2. 整体设计与核心思路拆解2.1 为什么选AC自动机而不是其他方案先说说为什么这道题非得用AC自动机。假设文本串长度是N模式串数量是M每个模式串平均长度是L。如果用最朴素的思路对每个模式串单独跑一遍KMP时间复杂度是O(M*(NL))。当M和N都达到10^5级别的时候这个量级直接爆炸。AC自动机的价值在于把所有模式串建成一棵trie树然后通过fail指针把匹配过程压缩成一次遍历文本串整体复杂度控制在O(N 总模式串长度 匹配次数)这个级别。但这里有个容易被忽略的点AC自动机在匹配阶段每走到一个节点需要沿着fail链往上跳统计所有以当前节点结尾的模式串。如果fail链很长匹配阶段的复杂度会退化。所以实际实现的时候通常会把统计信息预处理到节点上匹配时直接取避免每次都跳fail链。这道题因为要区分重叠和不重叠预处理的方式需要调整。2.2 重叠与不重叠的本质区别重叠匹配的意思是只要模式串在文本中出现不管两次出现是否有位置交叉都计数。比如文本是aaaa模式串是aa允许重叠的话出现位置是[1,2]、[2,3]、[3,4]共3次。不重叠的话第一次匹配占用了位置1和2下一次匹配必须从位置3开始所以只有[1,2]和[3,4]两次。这个区别在AC自动机上的体现是允许重叠时每次匹配到模式串结尾直接给计数加一不允许重叠时需要记录该模式串上一次匹配的结束位置只有当前匹配的起始位置严格大于上一次结束位置才计数并更新结束位置。关键在于AC自动机在文本串上跑的时候匹配到某个节点这个节点可能对应多个模式串因为fail链上的节点也可能是模式串结尾。所以每个模式串节点都需要独立维护自己的“上一次结束位置”。这就是为什么需要在节点上开额外的数组来记录状态。2.3 节点信息的组织方式我的做法是在trie树的每个节点上维护以下信息fail失配指针标准AC自动机必备。is_end标记该节点是否是某个模式串的结尾如果是记录模式串的编号。last_pos该节点对应的模式串上一次匹配的结束位置初始化为-1。cnt_overlap允许重叠的计数。cnt_non_overlap不允许重叠的计数。这里有个细节多个模式串可能共享同一个节点比如模式串ab和b可能在某些trie结构下结尾于同一节点所以is_end不能只存一个布尔值需要存模式串编号的列表。我用vector来存因为模式串数量不会特别大vector的开销可以接受。另一个细节是last_pos和两个计数数组只需要在模式串结尾节点上有效中间节点不需要维护。但为了代码简洁我直接在节点结构体里都开上空间换时间避免匹配时频繁判断节点类型。2.4 匹配阶段的处理逻辑匹配阶段遍历文本串的每个字符沿着trie树走遇到失配就跳fail指针。每到达一个节点需要沿着fail链向上检查所有可能是模式串结尾的节点。但前面说了直接跳fail链可能退化所以我的做法是在构建fail指针的时候把每个节点的fail链上最近的“模式串结尾节点”信息预处理到一个last_end指针里匹配时直接沿着last_end跳跳过中间的非结尾节点。对于每个匹配到的模式串结尾节点处理逻辑分两种情况如果标记是0允许重叠cnt_overlap直接加一。如果标记是1不允许重叠设当前匹配的起始位置为pos - len 1其中pos是当前文本串位置len是该模式串长度。如果pos - len 1 last_pos则cnt_non_overlap并更新last_pos pos。这里pos是从0开始还是从1开始会影响判断条件我习惯从0开始所以条件是pos - len 1 last_pos初始last_pos -1这样第一次匹配时pos - len 1 0 -1条件成立。3. 核心细节解析与实操要点3.1 Trie树的构建细节建trie树的时候每个节点用一个结构体表示包含一个大小为26的next数组假设只处理小写字母以及前面提到的那些辅助信息。插入模式串的时候沿着字符逐个走不存在就新建节点最后在结尾节点上把模式串编号push到is_end列表里。这里有个容易出错的地方模式串可能重复。比如输入里有两个相同的模式串但标记不同。这时候它们会共享同一个结尾节点is_end列表里会有两个编号。匹配的时候这个节点需要同时更新两个模式串的计数。所以is_end用vector存编号是必要的不能只存一个。另一个细节是节点数量的预估。模式串总长度不超过10^5的话节点数最多也是10^5 1。我习惯开maxn 100005的数组实际用的时候根据题目数据范围调整。如果模式串总长度可能达到610^5那数组要开到610^5 5否则会越界。3.2 Fail指针的构建与优化Fail指针的构建用BFS。根节点的所有直接子节点的fail指向根节点然后逐层往下处理。对于每个节点u遍历它的所有子节点v字符为c如果v存在则v的fail指向u的fail节点的c子节点如果v不存在直接把u的fail节点的c子节点作为u的c子节点路径压缩这是AC自动机常用的优化。这个路径压缩的优化很关键它让匹配阶段不需要while循环跳fail直接走next数组就行。但要注意压缩之后原来的trie结构被改变了is_end信息需要提前处理好不能在匹配时依赖原始trie结构。构建完fail指针后还需要预处理last_end指针。对于每个节点如果它的fail节点是模式串结尾那last_end就指向fail节点否则last_end指向fail节点的last_end。这个预处理可以在BFS过程中顺便完成。3.3 重叠计数的实现要点允许重叠的计数相对简单匹配到模式串结尾节点时直接加一。但要注意一个节点可能对应多个模式串需要遍历is_end列表对每个模式串都加一。如果模式串标记是0就更新cnt_overlap如果标记是1就按不重叠逻辑处理。这里有个性能上的考量如果is_end列表很长每次匹配都要遍历一遍可能影响效率。但实际上同一个节点对应的模式串数量不会太多因为模式串总长度有限共享同一结尾节点的模式串数量受限于总长度。所以直接遍历是可以接受的。3.4 不重叠计数的实现要点不重叠计数的核心是维护last_pos。每次匹配到模式串结尾计算当前匹配的起始位置start pos - len 1如果start last_pos则计数加一并更新last_pos pos。注意这里更新的是pos也就是当前匹配的结束位置而不是起始位置。因为下一次匹配必须从当前结束位置之后开始所以用结束位置作为边界。这里有个容易搞混的地方如果模式串长度为1那么start pos条件变成pos last_pos也就是当前位置必须严格大于上一次匹配位置。这是对的因为长度为1的模式串不重叠意味着不能连续匹配同一个位置。另一个细节是last_pos的初始值设为-1。如果设为0当模式串在文本开头匹配时start 0条件0 0不成立会漏掉第一次匹配。所以初始值必须是-1或者更小的负数。3.5 多模式串共享节点的处理前面提到多个模式串可能共享同一个结尾节点。这种情况下每个模式串有独立的标记和独立的last_pos。所以last_pos不能存在节点上而应该存在模式串上。我的做法是开一个全局数组last_pos_per_pattern按模式串编号索引而不是存在节点结构体里。同样cnt_overlap和cnt_non_overlap也按模式串编号索引而不是按节点索引。这样即使多个模式串共享节点它们的计数也是独立的。这个设计调整很重要我一开始把last_pos存在节点上结果遇到重复模式串的时候计数就乱了。后来改成按模式串编号存问题解决。4. 实操过程与核心环节实现4.1 节点结构体定义struct Node { int next[26]; int fail; int last_end; vectorint is_end; Node() { memset(next, -1, sizeof(next)); fail 0; last_end 0; is_end.clear(); } };这里next初始化为-1表示不存在fail和last_end初始为0根节点。is_end存模式串编号。4.2 插入模式串void insert(const string s, int id) { int u 0; for (char c : s) { int idx c - a; if (tree[u].next[idx] -1) { tree[u].next[idx] tot; tree[tot] Node(); } u tree[u].next[idx]; } tree[u].is_end.push_back(id); }注意每次新建节点时要初始化因为数组是复用的不清空会有残留数据。4.3 构建Fail指针void build() { queueint q; for (int i 0; i 26; i) { if (tree[0].next[i] ! -1) { int v tree[0].next[i]; tree[v].fail 0; tree[v].last_end 0; q.push(v); } else { tree[0].next[i] 0; } } while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i 26; i) { int v tree[u].next[i]; if (v ! -1) { tree[v].fail tree[tree[u].fail].next[i]; tree[v].last_end tree[tree[v].fail].is_end.empty() ? tree[tree[v].fail].last_end : tree[v].fail; q.push(v); } else { tree[u].next[i] tree[tree[u].fail].next[i]; } } } }这里last_end的预处理逻辑是如果fail节点本身是模式串结尾那last_end指向fail节点否则继承fail节点的last_end。这样匹配时沿着last_end跳就能直接找到所有模式串结尾节点跳过中间的非结尾节点。4.4 匹配文本串void query(const string text) { int u 0; for (int pos 0; pos text.size(); pos) { int idx text[pos] - a; u tree[u].next[idx]; int temp u; while (temp ! 0) { if (!tree[temp].is_end.empty()) { for (int id : tree[temp].is_end) { if (mark[id] 0) { cnt_overlap[id]; } else { int len pattern_len[id]; int start pos - len 1; if (start last_pos[id]) { cnt_non_overlap[id]; last_pos[id] pos; } } } } temp tree[temp].last_end; } } }这里temp沿着last_end跳每次跳到一个模式串结尾节点就处理该节点上的所有模式串。注意while循环的条件是temp ! 0因为根节点不是任何模式串的结尾。4.5 参数计算与选择过程模式串长度pattern_len[id]在插入时记录因为不重叠计数需要用到。last_pos[id]初始化为-1cnt_overlap[id]和cnt_non_overlap[id]初始化为0。文本串长度可能达到10^5模式串总长度也可能达到10^5所以整体时间复杂度是O(N 总模式串长度 匹配次数)。匹配次数在最坏情况下是N * 平均fail链长度但由于last_end的优化实际跳转次数远小于N * 链长。空间复杂度是O(节点数 * 26 模式串数量)节点数最多是总模式串长度1所以空间也是可接受的。4.6 完整代码框架#include bits/stdc.h using namespace std; const int MAXN 100005; struct Node { int next[26]; int fail; int last_end; vectorint is_end; Node() { memset(next, -1, sizeof(next)); fail 0; last_end 0; is_end.clear(); } }; Node tree[MAXN * 6]; int tot; int mark[MAXN]; int pattern_len[MAXN]; int last_pos[MAXN]; int cnt_overlap[MAXN]; int cnt_non_overlap[MAXN]; void init() { tot 0; tree[0] Node(); memset(mark, 0, sizeof(mark)); memset(pattern_len, 0, sizeof(pattern_len)); memset(last_pos, -1, sizeof(last_pos)); memset(cnt_overlap, 0, sizeof(cnt_overlap)); memset(cnt_non_overlap, 0, sizeof(cnt_non_overlap)); } void insert(const string s, int id) { int u 0; for (char c : s) { int idx c - a; if (tree[u].next[idx] -1) { tree[u].next[idx] tot; tree[tot] Node(); } u tree[u].next[idx]; } tree[u].is_end.push_back(id); pattern_len[id] s.size(); } void build() { queueint q; for (int i 0; i 26; i) { if (tree[0].next[i] ! -1) { int v tree[0].next[i]; tree[v].fail 0; tree[v].last_end 0; q.push(v); } else { tree[0].next[i] 0; } } while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i 26; i) { int v tree[u].next[i]; if (v ! -1) { tree[v].fail tree[tree[u].fail].next[i]; tree[v].last_end tree[tree[v].fail].is_end.empty() ? tree[tree[v].fail].last_end : tree[v].fail; q.push(v); } else { tree[u].next[i] tree[tree[u].fail].next[i]; } } } } void query(const string text) { int u 0; for (int pos 0; pos (int)text.size(); pos) { int idx text[pos] - a; u tree[u].next[idx]; int temp u; while (temp ! 0) { if (!tree[temp].is_end.empty()) { for (int id : tree[temp].is_end) { if (mark[id] 0) { cnt_overlap[id]; } else { int len pattern_len[id]; int start pos - len 1; if (start last_pos[id]) { cnt_non_overlap[id]; last_pos[id] pos; } } } } temp tree[temp].last_end; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); string text; int n; int case_num 0; while (cin text) { init(); cin n; for (int i 0; i n; i) { cin mark[i]; string s; cin s; insert(s, i); } build(); query(text); cout Case case_num endl; for (int i 0; i n; i) { if (mark[i] 0) { cout cnt_overlap[i] endl; } else { cout cnt_non_overlap[i] endl; } } } return 0; }这个框架可以直接拿去用只需要根据题目数据范围调整MAXN的大小。注意tree数组的大小是MAXN * 6因为模式串总长度可能达到6*10^5节点数最多是总长度1。5. 常见问题与排查技巧实录5.1 计数结果偏小或偏大最常见的问题是计数结果不对。如果允许重叠的计数偏小检查is_end列表是否完整有没有漏掉共享节点的模式串。如果偏大检查是否在同一个位置重复计数了比如last_end跳转时重复访问了同一个节点。不重叠计数偏小通常是last_pos的初始值设成了0而不是-1导致第一次匹配被跳过。偏大则是last_pos更新成了起始位置而不是结束位置导致下一次匹配的边界判断错误。5.2 数组越界或段错误节点数组开小了是最常见的原因。模式串总长度如果是610^5节点数最多是610^51但tree数组如果只开了10^5插入过程中就会越界。建议根据题目数据范围开数组宁可开大一点。另一个原因是next数组初始化成了-1但在BFS过程中被改成了0如果后续代码依赖-1来判断节点是否存在就会出错。所以BFS之后不能再依赖next的-1值来判断子节点是否存在。5.3 Fail指针跳转死循环如果last_end的预处理逻辑写错了可能导致last_end指向自己或者形成环匹配时就会死循环。检查last_end的赋值逻辑根节点的last_end是0其他节点的last_end要么指向fail节点如果fail节点是模式串结尾要么继承fail节点的last_end。确保不会出现last_end指向自己的情况。5.4 多组测试数据的初始化问题这道题是多组测试数据每组数据之间需要完全重置状态。init()函数里要把tot重置为0tree[0]重新初始化所有全局数组清零。如果漏掉了某个数组的重置上一组数据的结果会污染下一组。我踩过的坑是last_pos数组忘了重置导致第二组数据的不重叠计数全错。后来在init()里统一用memset重置所有数组问题解决。5.5 常见问题速查表问题现象可能原因排查方法重叠计数偏小is_end列表不完整检查插入时是否所有模式串都push了编号不重叠计数偏小last_pos初始值为0改为-1不重叠计数偏大last_pos更新为起始位置改为更新结束位置段错误节点数组开小根据总模式串长度调整MAXN死循环last_end成环检查预处理逻辑多组数据结果污染全局数组未重置在init()中memset所有数组5.6 性能优化的几个技巧如果匹配阶段超时可以考虑以下优化把is_end从vector改成数组加计数减少vector遍历开销。如果模式串数量很大可以把cnt_overlap和cnt_non_overlap合并成一个数组用标记区分。文本串很长时用getline或者cin加sync_with_stdio(false)加速输入。我实测下来上面的代码在总模式串长度10^5、文本串长度10^5的情况下运行时间在100ms以内完全够用。如果数据范围更大可以考虑把next数组从int改成short减少内存占用提高缓存命中率。5.7 一个容易忽略的边界情况如果模式串为空串插入时直接就在根节点上push了编号。但根节点的last_end是0匹配时while(temp ! 0)不会进入循环所以空串永远不会被计数。题目一般不会给空串但如果给了需要特殊处理。我的做法是在插入时判断如果模式串为空直接记录计数为文本串长度1允许重叠或者1不允许重叠不放进trie树。另一个边界是文本串为空这时候所有计数都是0直接输出即可。6. 从这道题延伸出的匹配问题思考AC自动机处理重叠与不重叠匹配本质上是在自动机的状态转移过程中附加了额外的约束条件。允许重叠时约束是“无”每次匹配都计数不允许重叠时约束是“当前匹配起始位置大于上一次匹配结束位置”。这个思路可以推广到其他类似的约束场景比如“匹配之间至少间隔k个字符”“匹配不能交叉”等。实现上的关键是把约束条件转化为节点或模式串上的状态变量在匹配过程中动态更新。状态变量的初始值和更新时机需要仔细设计否则容易出现边界错误。我在调试这道题的时候把last_pos的初始值从0改成-1从起始位置改成结束位置这两处改动花了最多时间定位。如果你已经理解了上面的内容可以试着把不重叠的条件改成“匹配之间至少间隔1个字符”看看代码需要怎么调整。这个练习能帮你更深入地理解AC自动机匹配阶段的控制逻辑。最后分享一个小技巧写这类题目的时候先在纸上画一棵简单的trie树标出fail指针和last_end指针然后手动模拟一遍文本串的匹配过程把每个位置的计数变化写下来。这个过程比直接调试代码快得多尤其是当你不确定边界条件的时候。