AC自动机
程序员文章站
2022-06-06 17:43:37
...
刚学 ac自动机,其实就是Tire的扩展,外加一个 fail指针,避免每次从树根遍历,fail指针指向当前字符串最长的后缀。看图吧
两个字符串:
abc
bc
建完字典树之后:
加入fail指针:
没有后缀的话 指向根节点,比如 abc c的fail指针我们先找 bc 没有的话 找c 还没有的话就指向根
加个题
HDU 2222
#include <bits/stdc++.h>
using namespace std;
const int Max_P = 500005;
struct AC{
int size;
struct node
{
int next[26];
int fail, cnt;
}stateTable[Max_P];
void init(){//初始化
size = 1;
for(int i = 0; i < Max_P; i ++){
memset(stateTable[i].next, 0 , sizeof stateTable[i].next);
stateTable[i].fail = stateTable[i].cnt = 0;
}
}
void build(){//构建fail树,bfs()
stateTable[0].fail = -1;
queue<int> q;
q.push(0);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = 0; i < 26;i ++){
if(stateTable[x].next[i]){
if(x == 0) stateTable[stateTable[x].next[i]].fail = 0;
else {
int v = stateTable[x].fail;
while(v != -1){
if(stateTable[v].next[i]){
stateTable[stateTable[x].next[i]].fail = stateTable[v].next[i];
break;
}
v = stateTable[v].fail;
}
if(v == -1) stateTable[stateTable[x].next[i]].fail = 0;
}
q.push(stateTable[x].next[i]);
}
}
}
}
void insert(char *S){//建立字典树
int len = strlen(S);
int now = 0;
for(int i = 0; i < len; i ++){
if(!stateTable[now].next[S[i] - 'a']) stateTable[now].next[S[i] - 'a'] = size ++;
now = stateTable[now].next[S[i] - 'a'];
}
stateTable[now].cnt ++;
}
int Get(int x){
int res = 0;
while(x){
res = res + stateTable[x].cnt;
stateTable[x].cnt = 0;//看题意是否需要置零
x = stateTable[x].fail;
}
return res;
}
int match(char *S){//模式串匹配
int len = strlen(S);
int now = 0;
int res = 0;
for(int i = 0 ;i < len; i ++){
if(stateTable[now].next[S[i] - 'a']){
now = stateTable[now].next[S[i] - 'a'];
}
else{
int v = stateTable[now].fail;
while(v != -1 && !stateTable[v].next[S[i] - 'a']) v = stateTable[v].fail;
if(v == -1) now = 0;
else {
now = stateTable[v].next[S[i] - 'a'];
}
}
if(stateTable[now].cnt)//获得答案,当前如果是一个前缀就加入
res += Get(now);
}
return res;
}
}ans;
char S[1000006];
int main()
{
int t;
cin >> t;
while(t --){
int n;
scanf("%d",&n);
ans.init();
for(int i = 0; i < n; i ++){
scanf("%s",S);
ans.insert(S);
}
ans.build();
scanf("%s",S);
printf("%d\n",ans.match(S));
}
}
fail树的应用有点类似拓扑的样子,如果 i 是 j 的后缀,那么j的 fail 指针会跳回到i,那么i.cnt= i .cnt + j.cnt, 同时记录一下 i 在其他串中充当前缀的次数
#include <bits/stdc++.h>
using namespace std;
const int Max_P = 500005;
queue<int> p;
struct AC{
int size;
int num[1000006];
int len1 = 0;
struct node
{
int next[26];
int fail, cnt;
}stateTable[1000006];
void init(){
size = 1;
for(int i = 0; i < 1000006; i ++){
memset(stateTable[i].next, 0 , sizeof stateTable[i].next);
stateTable[i].fail = stateTable[i].cnt = 0;
}
}
void build(){
stateTable[0].fail = -1;
queue<int> q;
q.push(0);
while(!q.empty()){
int x = q.front();
q.pop();
num[++len1] = x;
for(int i = 0; i < 26;i ++){
if(stateTable[x].next[i]){
if(x == 0) stateTable[stateTable[x].next[i]].fail = 0;
else {
int v = stateTable[x].fail;
while(v != -1){
if(stateTable[v].next[i]){
stateTable[stateTable[x].next[i]].fail = stateTable[v].next[i];
break;
}
v = stateTable[v].fail;
}
if(v == -1) stateTable[stateTable[x].next[i]].fail = 0;
}
q.push(stateTable[x].next[i]);
}
}
}
for(int i = len1; i >= 1; i --){
stateTable[stateTable[num[i]].fail].cnt+= stateTable[num[i]].cnt;
}
}
void insert(char *S){
int len = strlen(S);
int now = 0;
for(int i = 0; i < len; i ++){
if(!stateTable[now].next[S[i] - 'a']) stateTable[now].next[S[i] - 'a'] = size ++;
now = stateTable[now].next[S[i] - 'a'];
stateTable[now].cnt ++;
}
p.push(now);
}
}ans;
char S[1000006];
int main()
{
int n;
scanf("%d",&n);
ans.init();
for(int i = 0; i < n; i ++){
scanf("%s",S);
ans.insert(S);
}
ans.build();
while(!p.empty()){
cout << ans.stateTable[p.front()].cnt << endl;
p.pop();
}
}