目录
BZOJ3172 单词题解ｃｏｄｅ
BZOJ3172 单词
题目传送门
题解
裸的AC自动机，构造出AC自动机之后，将每一个节点的出现次数都累加到它的\(fail\)节点上去，最后得到的就是答案了。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=1e6+500;
int n,w[210];
char s[maxn];
/*==================Define Area================*/
struct ac_automaton{
int tot,ch[maxn][26],fail[maxn],q[maxn],head,tail,sum[maxn];
void insert(int &x){
int p=0;
int len=strlen(s);
for (int i=0;i<len;i++){
if (!ch[p][s[i]-'a']) ch[p][s[i]-'a']=++tot;
++sum[p=ch[p][s[i]-'a']];
}
x=p;
}
void getfail(){
head=0,q[tail=1],fail[0]=-1;
while (head!=tail){
int x=q[++head];
for (int i=0;i<26;i++){
if (ch[x][i]) q[++tail]=ch[x][i],fail[ch[x][i]]=x==0?0:ch[fail[x]][i];
else ch[x][i]=x==0?0:ch[fail[x]][i];
}
}
}
void work(){
for (int i=tail;i;i--) sum[fail[q[i]]]+=sum[q[i]];
for (int i=1;i<=n;i++) printf("%d\n",sum[w[i]]);
}
}T;
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%s",s),T.insert(w[i]);
T.getfail(),T.work();
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9432779.html
