信奥赛C++提高组csp-s之AC自动机详解

信奥赛C++提高组csp-s之AC自动机详解

1、什么是AC自动机？

AC自动机（Aho-Corasick Automaton）是一种经典的多模式匹配算法，可以在文本串中同时查找多个模式串的出现位置。它结合了：

• Trie树：用于存储所有模式串
• KMP算法：通过失败指针实现高效跳转

时间复杂度：O(n + m + z)，其中n是文本串长度，m是所有模式串总长度，z是匹配次数

2、AC自动机原理详解

核心思想

1. 构建Trie树：将所有模式串插入到一棵Trie树中
2. 构建失败指针：为每个节点建立fail指针，指向当匹配失败时应该跳转的位置
3. 文本匹配：在文本串上进行匹配，利用fail指针实现高效跳转

研究案例

题目描述

给定n nn个模式串s i s_isi​和一个文本串t tt，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

输入格式

第一行是一个整数，表示模式串的个数n nn。
第2 22到第( n + 1 ) (n + 1)(n+1)行，每行一个字符串，第( i + 1 ) (i + 1)(i+1)行的字符串表示编号为i ii的模式串s i s_isi​。
最后一行是一个字符串，表示文本串t tt。

输出格式

输出一行一个整数表示答案。

输入输出样例 1

输入 1

3 a aa aa aaa

输出 1

3

输入输出样例 2

输入 2

4 a ab ac abc abcd

输出 2

3

输入输出样例 3

输入 3

2 a aa aa

输出 3

2

说明/提示

样例 1 解释

s 2 s_2s2​与s 3 s_3s3​编号（下标）不同，因此各自对答案产生了一次贡献。

样例 2 解释

s 1 s_1s1​，s 2 s_2s2​，s 4 s_4s4​都在串abcd里出现过。

数据规模与约定

• 对于50 % 50\%50%的数据，保证n = 1 n = 1n=1。
• 对于100 % 100\%100%的数据，保证1 ≤ n ≤ 10 6 1 \leq n \leq 10^61≤n≤106，1 ≤ ∣ t ∣ ≤ 10 6 1 \leq |t| \leq 10^61≤∣t∣≤106，1 ≤ ∑ i = 1 n ∣ s i ∣ ≤ 10 6 1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^61≤i=1∑n​∣si​∣≤106。s i , t s_i, tsi​,t中仅包含小写字母。

思路分析

步骤1：构建Trie树

// 插入模式串"she"到Trie树根节点(0)↓s(创建节点1，深度1)↓h(创建节点2，深度2)↓e(创建节点3，深度3，标记为结尾)

步骤2：构建失败指针（关键步骤）

失败指针定义：

• 当当前节点匹配失败时，应该回退到哪个节点继续尝试匹配。
• 更具体地，对于Trie树中的每个节点（代表某个字符串前缀），它的失败指针指向另一个节点，该节点代表的字符串是当前节点字符串的最长后缀，并且这个后缀同时也是某个模式串的前缀。

失败指针的本质：

失败指针实际上构建了一个状态转移图，其中：

• 每个节点代表一个"匹配状态"
• 成功匹配时沿着Trie边移动
• 匹配失败时沿着失败指针移动

构建规则：

1. 根节点的失败指针指向自己
2. 根节点的直接子节点的失败指针指向根节点
3. 其他节点u的失败指针：
   • 设u的父节点为p，通过字符c到达u（即 tr[ p ] [ c ] [p][c][p][c]= u）
   • 先找到p的失败指针指向的节点f = fail[p]
   • 如果f有通过字符c到达的子节点v，则fail[u] = v
   • 否则，继续找f的失败指针，直到根节点

步骤3：文本匹配

遍历文本串中的每个字符：

1. 从当前节点出发，沿着Trie树向下匹配
2. 如果匹配失败，沿着fail指针跳转，直到可以匹配或回到根节点
3. 每到达一个节点，沿着它的fail链统计所有模式串结尾

详细过程分析

以模式串"she"、“he”、“her”、"his"为例分析

1. 首先构建Trie树

构建后的Trie树结构：

根节点(0) ├── s (1) │ └── h (2) │ └── e (3) ["she"] └── h (4) ├── e (5) ["he"] │ └── r (6) ["her"] └── i (7) └── s (8) ["his"]

节点编号说明：

• 0: 根节点
• 1: ‘s’
• 2: ‘s’->‘h’
• 3: ‘s’->‘h’->‘e’ (匹配"she")
• 4: ‘h’
• 5: ‘h’->‘e’ (匹配"he")
• 6: ‘h’->‘e’->‘r’ (匹配"her")
• 7: ‘h’->‘i’
• 8: ‘h’->‘i’->‘s’ (匹配"his")

2. 构建失败指针的BFS过程

第1层：根节点的子节点

• 节点1(‘s’)：

  • 父节点：根节点(0)
  • 父节点的fail指针：根节点(0)
  • 检查根节点是否有’s’子节点：没有
  • 继续沿fail指针向上：根节点的fail指向自己，结束
  • 设置节点1的fail指针 = 根节点(0)

• 节点4(‘h’)：

  • 父节点：根节点(0)
  • 检查根节点是否有’h’子节点：有（节点4自身），但这不是我们需要的
  • 继续：根节点的fail指向自己，结束
  • 设置节点4的fail指针 = 根节点(0)

第2层：处理第一层节点的子节点

• 节点2(‘h’)（父节点是节点1）：

  • 父节点1的fail指针：根节点(0)
  • 检查根节点是否有’h’子节点：有（节点4）
  • 设置节点2的fail指针 = 节点4

• 节点5(‘e’)（父节点是节点4）：

  • 父节点4的fail指针：根节点(0)
  • 检查根节点是否有’e’子节点：没有
  • 继续沿fail向上：根节点的fail指向自己，结束
  • 设置节点5的fail指针 = 根节点(0)

• 节点7(‘i’)（父节点是节点4）：

  • 父节点4的fail指针：根节点(0)
  • 检查根节点是否有’i’子节点：没有
  • 设置节点7的fail指针 = 根节点(0)

第3层：处理第二层节点的子节点

• 节点3(‘e’)（父节点是节点2）：

  • 父节点2的fail指针：节点4
  • 检查节点4是否有’e’子节点：有（节点5）
  • 设置节点3的fail指针 = 节点5
  • 重要：节点3匹配"she"，节点5匹配"he"，"he"是"she"的后缀

• 节点6(‘r’)（父节点是节点5）：

  • 父节点5的fail指针：根节点(0)
  • 检查根节点是否有’r’子节点：没有
  • 设置节点6的fail指针 = 根节点(0)

• 节点8(‘s’)（父节点是节点7）：

  • 父节点7的fail指针：根节点(0)
  • 检查根节点是否有’s’子节点：有（节点1）
  • 设置节点8的fail指针 = 节点1

3. 最终的失败指针表

节点	字符	父节点	fail指针	匹配模式
0	根	-	0	-
1	s	0	0	-
2	h	1	4	-
3	e	2	5	she
4	h	0	0	-
5	e	4	0	he
6	r	5	0	her
7	i	4	0	-
8	s	7	1	his

4. 关键分析

为什么节点3的fail指向节点5？

• 节点3的路径：“s”->“h”->“e” (“she”)
• 节点5的路径：“h”->“e” (“he”)
• "he"是"she"的后缀，所以匹配失败时应该退到匹配"he"的状态

为什么节点8的fail指向节点1？

• 节点8的路径：“h”->“i”->“s” (“his”)
• 节点1的路径：“s”
• 虽然"s"不是"his"的后缀，但是：
  1. 节点7(‘i’)的fail指向根节点
  2. 根节点有’s’子节点（节点1）
  3. 所以尝试在根节点匹配’s’，成功找到节点1

5. 匹配示例

假设文本是"sher"，匹配过程：

1. ‘s’ -> 节点1
2. ‘h’ -> 节点2
3. ‘e’ -> 节点3（匹配"she"）
   • 检查fail链：节点3->节点5（匹配"he"）
4. ‘r’：从节点3出发，没有’r’子节点
   • 跳转到节点3.fail = 节点5
   • 节点5有’r’子节点（节点6）
   • ‘r’ -> 节点6（匹配"her"）

一次匹配，找到两个模式串：“she"和"he”！

6. 时间复杂度分析

• Trie构建：O(∑L)，L是模式串长度
• 失败指针构建：O(∑L × |Σ|)，|Σ|是字符集大小
• 匹配：O(n + z)，n是文本长度，z是匹配次数

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1000010;// 最大节点数constintSIGMA=26;// 字符集大小（小写字母）inttr[MAXN][SIGMA];// Trie树，tr[u][c]表示节点u通过字符c到达的子节点intcnt[MAXN];// 记录以节点i结尾的模式串数量intfail[MAXN];// 失败指针intq[MAXN];// 数组模拟队列（BFS用）intidx=0;// 当前节点编号，0表示根节点// 初始化AC自动机voidinit(){memset(tr,0,sizeof(tr));memset(cnt,0,sizeof(cnt));memset(fail,0,sizeof(fail));idx=0;}// 向Trie树中插入一个模式串voidinsert(constchar*str){intp=0;// 从根节点开始for(inti=0;str[i];i++){intc=str[i]-'a';// 将字符转换为0-25的数字if(!tr[p][c]){// 如果当前节点没有这个子节点tr[p][c]=++idx;// 创建新节点}p=tr[p][c];// 移动到子节点}cnt[p]++;// 标记模式串结尾，可能有多个模式串在同一节点结束}// 构建失败指针（BFS层次遍历）voidbuild(){inthead=0,tail=0;// 队列头尾指针// 第一层节点（根节点的子节点）的fail指针都指向根节点for(inti=0;i<SIGMA;i++){if(tr[0][i]){q[tail++]=tr[0][i];// 将根节点的子节点入队}}// BFS遍历Trie树while(head<tail){intu=q[head++];// 取出队首节点// 遍历当前节点的所有子节点for(inti=0;i<SIGMA;i++){if(tr[u][i]){// 如果存在子节点v// 子节点v的失败指针 = 父节点u的失败指针通过字符i到达的节点fail[tr[u][i]]=tr[fail[u]][i];q[tail++]=tr[u][i];// 将子节点入队}else{// 如果不存在子节点，创建虚拟边（Trie图优化）// 这样在匹配时不需要频繁跳转fail指针tr[u][i]=tr[fail[u]][i];}}}}// 在文本串中查询模式串出现次数intquery(constchar*str){intp=0;// 从根节点开始intres=0;// 匹配到的模式串总数for(inti=0;str[i];i++){intc=str[i]-'a';// 当前字符p=tr[p][c];// 沿着Trie树向下走// 沿着失败指针链统计所有匹配的模式串intj=p;while(j&&cnt[j]!=-1){// 未访问过且不是根节点res+=cnt[j];// 累加匹配到的模式串数量cnt[j]=-1;// 标记已访问，防止重复统计j=fail[j];// 跳转到下一个失败指针}}returnres;}intmain(){init();// 初始化AC自动机intn;scanf("%d",&n);// 读取模式串数量// 插入所有模式串charpattern[1000010];for(inti=0;i<n;i++){scanf("%s",pattern);insert(pattern);}build();// 构建失败指针// 读取文本串并查询chartext[1000010];scanf("%s",text);intresult=query(text);printf("%d\n",result);// 输出结果return0;}

关键点解析

1. Trie图优化

// 普通AC自动机匹配时需要不断跳转fail指针：while(p&&!tr[p][c])p=fail[p];// Trie图优化后，可以直接转移：p=tr[p][c];// 已经预处理好不存在的边

这种优化将AC自动机变成了确定有限状态自动机（DFA），匹配时不需要while循环跳转。

2. 失败指针的构建（BFS顺序）

失败指针必须按BFS顺序构建，因为：

• 需要保证当前节点的父节点的fail指针已经计算完成
• BFS按层遍历，确保深度小的节点先处理

3. 统计去重

在本案例中，同一个模式串只统计一次，所以匹配后需要标记：

cnt[j]=-1;// 标记已访问

4. 复杂度分析

• 构建Trie树：O(Σ模式串总长度)
• 构建fail指针：O(节点数 × 字符集大小)
• 匹配：O(文本串长度 + 匹配次数)

5. 注意事项

1. 数组大小：节点数应 ≥ 所有模式串总长度 + 1
2. 字符集处理：根据题目调整字符集大小
3. 内存优化：可以使用链表或压缩存储节省空间
4. 多组数据：注意每次初始化所有数组

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、csp高频考点知识详解及案例实践：
  • CSP信奥赛C++之动态规划
  • CSP信奥赛C++之标准模板库STL
  • 信奥赛C++提高组csp-s知识详解及案例实践
• 四、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

---

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}