#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;
int ch[M][26],cnt[M],fail[M],tot;
void insert(char *s) {//字典树的建立
int p=0,len=strlen(s+1);
for(int i=1;i<=len;i++) {
int v=s[i]-'a';
if(ch[p][v]==0)ch[p][v]=++tot;
p=ch[p][v];
}
cnt[p]++;
}
void init() {
queue<int>q;
for(int i=0;i<26;i++)
if(ch[0][i])q.push(ch[0][i]);//对于第一层的点之间遍历
while(!q.empty()) {
int now=q.front();
q.pop();
for(int i=0;i<26;i++) {
if(ch[now][i]) {
fail[ch[now][i]]=ch[fail[now]][i];//找失落点
q.push(ch[now][i]);
}
else ch[now][i]=ch[fail[now]][i];//继承上一个点的状态
}
}
}
int query(char *s) {
int len=strlen(s+1);
int now=0,ans=0;
for(int i=1;i<=len;i++) {//从起点开始遍历
now=ch[now][s[i]-'a'];
for(int j=now;j&&cnt[j]!=-1;j=fail[j]) {
ans+=cnt[j];
cnt[j]=-1;//防止一个点重复遍历
}
}
return ans;
}
char s[M];
int main() {
int n;cin>>n;
for(int i=1;i<=n;i++) {
scanf("%s",s+1);
insert(s);
}//建树
init();
scanf("%s",s+1);
cout<<query(s)<<endl;//查找
return 0;
}
标签:AC,ch,int,char,自动机,模板
From: https://www.cnblogs.com/basicecho/p/17056464.html