Algorithm1.4 AC自动机
[TOC]
字符串 AC自动机
demo：AC自动机维护：
[he, his, hers, she]，要查询的单词：ahishers过程一：构建Trie树：
- node节点结构体：
- 当前节点的值
- 存放指向下一层node节点指针的List（最多26个=>26个字母）
- fail失效指针：用来找最长相同后缀，节省从头查找的时间
- 【特殊】对于是某一个p的结尾节点的，这个特殊的节点储存更多信息
- 利用一个bool数组来标记某一个节点是否是尾部节点【例如下图中的trie树双层圈的都是】
过程二：构建AC自动机
完善fail指针
过程三：输入待测字串进行测试
通过root往下查询某一个待测字串：
- 查找正确：
- 到双层圈的节点 => 完成完全匹配
- 未到双层圈的节点 => 完成部分(前缀)匹配
- 查找错误：
- 空指针 => 直接从root根节点就无法匹配
- 未找到双层圈的节点 => 完成部分(前缀)匹配
方法一：利用链表实现
数据结构：结构体和指向结构体的指针
方法二：利用数组实现
1、初始化trie树「trie[][]树，cnt[]数组判定节点是否是字典终止节点」
对应位置初始化上值，cnt数组进行初始化
2、初始化fail指针「当前节点nw，遍历到的当前节点nw的儿子pos」
对于当前节点，那么他的所有儿子节点就是for(i~[0, 26]) pos = trie[nw][i]表示所有儿子的值。
- 如果当前儿子为真儿子，那么
trie[nw][i]不为0 =>fail[pos] = trie[fail[nw]][i];对于当前节点nw的fail指针是已知的，所以就要利用当前nw节点的fail指针来更新他的所有儿子节点的fail指针 => 真儿子的fail指针指向当前节点的fail指针对应的指向方向的节点if (!fail[pos]) fail[pos] = 1;此时刷新出来的指向的方向不一定有值，也就是说有可能指向的那个也是空 => 就要替换成父节点else就正常赋值就好，赋成当前节点的fail指针指向的节点的对应方向
- 如果当前儿子为假儿子，可以将fail指针指向的节点相同方向的值赋过去（fail指针指向的节点有值是最好的，没有值也无所谓）相当于把fail指针指向的节点那棵树嫁接在了这个节点下边
3、利用AC自动机进行搜索「当前节点nw，pos」
板题：洛谷P3808 AC自动机（简单版）
https://www.luogu.com.cn/problem/P3808
题目大意：给出模式串的个数以及所有模式串，然后给出主串，问在主串中可以找到的模式串的个数（特殊：如果某一个模式串被多次匹配，那么只计算一次）
利用数组实现：AC代码
#include <iostream>
using namespace std;
const int maxnext = 27;
const int maxnode = 1e6+9;
char s[maxnode];
int n, tot = 1; // tot 链式结构的计数器
#include <queue>
#include <cstring>
struct AC_Machine {
int trie[maxnode][maxnext];
int fail[maxnode];
int cnt[maxnode];
inline void build_trie(char *s) {
int len = strlen(s+1), pos = 1;
for (int i = 1; i <= len; ++i) {
int ch_idx = s[i]-'a';
if (!trie[pos][ch_idx]) trie[pos][ch_idx] = ++tot; // 将新节点赋上计数器tot的值 => 计数器tot的值代表了每一个节点，是唯一的，tot不被重复
pos = trie[pos][ch_idx]; // 链式前向星，遍历的时候直接可以遍历这个父节点的所有有效子节点
}
cnt[pos]++;
}
inline void build_ac_machine() {
queue<int>q;
// 预处理，根节点的真儿子fail指针指向根节点，并且真儿子入队，准备后续的广搜
for (int i = 0; i < maxnext; ++i) {
int pos = trie[1][i];
if (pos) fail[pos] = 1; // 根节点的计数器tot的值为1
q.push(pos);
}
while (!q.empty()) {
int nw = q.front();q.pop();
for (int i = 0; i < maxnext; ++i) {
// 通过遍历一个节点的maxnext个子儿子的trie树值，查看哪个儿子的值是自身的id标号
int pos = trie[nw][i];
if (pos) { // 找到真儿子
fail[pos] = trie[fail[nw]][i]; // 把当前节点的真儿子节点的fail指针进行定向，定向到当前节点的fail指针指向的对应当前真儿子所指向的方向（如果有=>代表有的指；如果为空=>代表没得指）
if (!fail[pos]) fail[pos] = 1; // 如果没找到的话，全部赋回给根节点root，也就是计数器tot的值为1的点
q.push(pos);
} else { // 假儿子也要进行处理
trie[nw][i] = trie[fail[nw]][i]; // 如果当前节点的假儿子在fail指针进行定向的位置有值，也可以给赋过去
}
}
}
}
inline int find(char *s) {
int len = strlen(s+1), pos = 1, sum = 0;
for (int i = 1; i <= len; ++i) {
int ch_idx = s[i]-'a';
int nw = trie[pos][ch_idx];
while (nw && cnt[nw] != -1) {
sum += cnt[nw]; // 计算查找到的次数
cnt[nw] = -1; // 标记已经计算过
nw = fail[nw]; // 利用fail指针跳转到
}
pos = trie[pos][ch_idx];
}
return sum;
}
}acMachine;
int main() {
scanf("%d", &n);
while (n--) {
scanf("%s", s+1);
acMachine.build_trie(s);
}
acMachine.build_ac_machine();
scanf("%s", s+1);
printf("%d\n", acMachine.find(s));
return 0;
}
利用链式结构，实现AC自动机（通过添加一个map映射-将node和标记来进行映射，来判断节点所对应的模式串是否被标记过了）
#include <iostream>
using namespace std;
const int maxnext = 26;
int n, ans;
string p, t;
#include <vector>
struct node {
char val; // debug
vector<int> exist;
node * child[maxnext];
node * fail;
}*root;
#include <map>
map<node*, int> mp;
void build_trie(node * root) {
node * tem = root;
for (int i = 0; i < p.length(); ++i) {
int ch_idx = p[i]-'a';
if (tem->child[ch_idx] == NULL) tem->child[ch_idx] = new node();
tem = tem->child[ch_idx];
tem->val = p[i]; // 注意要等tem到下一个节点了再给赋值
}
tem->exist.push_back(p.length());
}
// 遍历trie树
void traverse(node * root) {
cout << root->val << " ";
for (int i = 0; i < maxnext; ++i)
if (root->child[i] != NULL) traverse(root->child[i]);
}
#include <queue>
queue<node*>q;
void build_ac_auto(node * root){
// init
for (int i = 0; i < maxnext; ++i)
if (root->child[i]) {
root->child[i]->fail = root;
q.push(root->child[i]);
}
// get fail
while (!q.empty()) {
node * nw = q.front();q.pop();
for (int i = 0; i < maxnext; ++i) {
if (nw->child[i]) {
node * ntnw = nw->child[i];
node * fafail = nw->fail;
while (fafail && !fafail->child[i]) fafail = fafail->fail;
if (!fafail) ntnw->fail = root;
else ntnw->fail = fafail->child[i];
if (ntnw->fail->exist.size())
for (int j = 0; j < ntnw->fail->exist.size(); ++j)
ntnw->exist.push_back(ntnw->fail->exist[j]);
q.push(ntnw);
}
}
}
}
void ac_auto_query(node * root) {
node * tem = root;
for (int i = 0; i < maxnext; ++i) {
int ch_idx = t[i]-'a';
while (tem->fail && !tem->child[ch_idx]) tem = tem->fail;
if (tem->child[ch_idx]) tem = tem->child[ch_idx];
else continue;
if(tem->exist.size() && !mp.count(tem)) ans++, mp[tem] = 1;
}
}
int main() {
scanf("%d", &n);
root = new node();
while (n--) {
cin>>p;
build_trie(root);
}
build_ac_auto(root);
cin>>t;
ac_auto_query(root);
printf("%d\n", ans);
return 0;
}
模版：洛谷P3796 AC自动机（加强版）
https://www.luogu.com.cn/problem/P3796
题目大意：同样是给出模式串的个数以及所有模式串，然后给出主串，问所有给定的模式串中在主串中找到次数最多的。