企业官网建设流程全解析

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*(N+L))。当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; vector<int> 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() { queue<int> 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]初始化为-1，cnt_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; vector<int> 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() { queue<int> 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^5+1，但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重置为0，tree[0]重新初始化，所有全局数组清零。如果漏掉了某个数组的重置，上一组数据的结果会污染下一组。

我踩过的坑是last_pos数组忘了重置，导致第二组数据的不重叠计数全错。后来在init()里统一用memset重置所有数组，问题解决。

5.5 常见问题速查表

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指针，然后手动模拟一遍文本串的匹配过程，把每个位置的计数变化写下来。这个过程比直接调试代码快得多，尤其是当你不确定边界条件的时候。