HDU 3065 AC自动机 裸题

中文题题意不再赘述

注意 失配数组 f  初始化一步到位

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;#define N 2000100
#define maxnode 50010
#define sigma_size 26
struct node{
char name[55];
int num;
}S[1101];
struct Trie{
int ch[maxnode][sigma_size];
int val[maxnode];
int f[maxnode];
int sz;
void init(){
sz=1;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
memset(f,0,sizeof(f));
val[0] = 0;
}
int idx(char c){
return c-'A';
}void Creat(char *s, int num){
int u = 0, len = strlen(s);
for(int i = 0; i < len; i++){
int c = idx(s[i]);
if(!ch[u][c]) ch[u][c] = sz++;
u = ch[u][c];
}
val[u] = num ; //u若是单词结尾则为 +1
}  int find(char *T){
int len = strlen(T);
int j = 0;
for(int i = 0; i < len; i++){
if(T[i]<'A' || T[i]>'Z'){ j = 0; continue;}
int c = idx(T[i]);
j = ch[j][c];
int temp = j;
while(temp && val[temp]){
S[ val[temp] ].num ++;
temp = f[ temp ];
}
}return 0;
}void getFail(){
queue<int> q;
//初始化队列
for(int c = 0; c < sigma_size; c++)
if(ch[0][c])q.push(ch[0][c]);while(!q.empty()){
int r = q.front(); q.pop();
for(int c = 0; c < sigma_size; c++){
int u = ch[r][c];
if(!u){ ch[r][c] = ch[f[r]][c]; continue; }
q.push(u);
int v = f[r];
while(v && !ch[v][c]) v = f[v]; //沿失配边追溯到可以匹配的(非原点)位置
f[u] = ch[v][c];
}
}
}
};
Trie ac;
char S1[N];int main(){
int n;
while(~scanf("%d",&n)){
ac.init();
for(int i = 1; i <= n; i++){
scanf("%s",S[i].name);
S[i].num = 0;
ac.Creat(S[i].name, i);
}
ac.getFail();scanf("%s",S1);
ac.find(S1);for(int i = 1; i <= n; i++)
if(S[i].num)
printf("%s: %d\n",S[i].name, S[i].num);}
return 0;
}