P3808
KMP用来求单模式串的匹配,AC自动机用来求多模式串的匹配。
就是给你n个模式串,再给你一个文本串,求有多少个模式串在文本串中出现过。
AC自动机的数据结构基于trie数,像KMP的nxt数组一样维护失配指针fail(寻找fail的过程是用bfs实现的),查询过程中不断向下匹配,匹配不了就往fail指针方向走。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct Trie {
int fail;//失配指针
int vis[30];//子节点的位置编号
int End;
}AC[N];
int n, tot = 0;
string s;
void build(string s) {
int len = s.length();
int p = 0;
for (int i = 0; i < len; i ++) {
if (AC[p].vis[s[i] - 'a'] == 0)
AC[p].vis[s[i] - 'a'] = ++ tot;
p = AC[p].vis[s[i] - 'a'];
}
AC[p].End ++;
}
void getfail() {
queue<int> q;
for (int i = 0; i < 26; i ++) {//处理第二层失配指针
if (AC[0].vis[i] != 0) {//该节点存在
AC[AC[0].vis[i]].fail = 0;//第二层都要指向根节点
q.push(AC[0].vis[i]);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < 26; i ++) {
if (AC[u].vis[i] != 0) {//该节点存在
AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
//令v = AC[u].vis[i] v是u的儿子,v的fail指向u的fail的相同字母的儿子
q.push(AC[u].vis[i]);
}
else AC[u].vis[i] = AC[AC[u].fail].vis[i];
//节点不存在就直接将u的儿子节点指向u的fail的相同字母的儿子
}
}
}
int query(string s) {//AC自动机匹配
int len = s.length();
int p = 0, ans = 0;
for (int i = 0; i < len; i ++) {
p = AC[p].vis[s[i] - 'a'];
for (int k = p; k && AC[k].End != -1; k = AC[k].fail) {
ans += AC[k].End;
AC[k].End = -1;//标记已走过
}
}
return ans;
}
int main() {
int T;
scanf("%d", &T);
while (T --) {
memset((void *) &AC, 0x00, sizeof(AC));
tot = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i ++) {
cin >> s;
build(s);
}
AC[0].fail = 0;//结束标志(根节点的失配指针一定指向自己)
getfail();//求失配指针
cin >> s;
cout << query(s) << '\n';
}
return 0;
}
标签:AC,int,++,vis,P3808,fail,节点,模板
From: https://www.cnblogs.com/YHxo/p/16782427.html