AC 自动机
AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的。
简要步骤
- 将所有的模式串构成一棵 Trie。
- 对 Trie 树上所有的结点构造失配指针。
然后就可以利用它进行多模式匹配了。
AC·code
#include<bits/stdc++.h>
#define I inline int
#define V inline void
#define ri register int
using namespace std;
const int N=1e6+5;
char x_x[155][75],c[N];
struct qwq{
int fail,cnt;
int nxt[26];
}tr[N];
int id;
V build(int tat){
cin>>x_x[tat];
int len=strlen(x_x[tat]);
int t=0;
for(int i=0;i<len;i++){
if(!tr[t].nxt[abs(x_x[tat][i]-'a')%26]){
tr[t].nxt[abs(x_x[tat][i]-'a')%26]=++id;
}
t=tr[t].nxt[abs(x_x[tat][i]-'a')%26];
}
tr[t].cnt=tat;
return;
}
V getfail(){
queue<int> q;
int t=0;
for(int i=0;i<26;i++){
if(tr[t].nxt[i]){
q.push(tr[t].nxt[i]);
}
}
while(!q.empty()){
t=q.front();q.pop();
for(int i=0;i<26;i++){
if(tr[t].nxt[i]){
tr[tr[t].nxt[i]].fail=tr[tr[t].fail].nxt[i];
q.push(tr[t].nxt[i]);
}
else{
tr[t].nxt[i]=tr[tr[t].fail].nxt[i];
}
}
}
return;
}
V find(int n){
cin>>c;
int ans[155]={0};
int len=strlen(c);
int s=1,t=0;
int iid[155]={0},tii=0;
iid[0]=1;
for(int i=0;i<len;i++){
t=tr[t].nxt[abs(c[i]-'a')%26];
for(int j=t;j;j=tr[j].fail){
ans[tr[j].cnt]++;
}
}
for(int i=2;i<=n;i++){
if(ans[i]>ans[s]){
s=i,tii=0,iid[0]=s;
}
else if(ans[i]==ans[s]){
iid[++tii]=i;
}
}
cout<<ans[s]<<"\n";
for(int i=0;i<=tii;i++){
cout<<x_x[iid[i]]<<"\n";
}
return;
}
int n;
V memsett(){
for(int i=0;i<=n;i++){
memset(tr[i].nxt,0,sizeof(tr[i].nxt));
tr[i].fail=tr[i].cnt=0;
}
return;
}
int main(){
cin>>n;
while(n){
memsett();
for(int i=1;i<=n;i++) build(i);
getfail();
find(n);
cin>>n;
}
return 0;
}