BZOJ 3172 [Tjoi2013]单词

题目大意

给你N个字符串,求每个字符串在所有字符串中出现的次数。

AC自动机裸题，就是自己和自己匹配罢了。注意如果匹配成功一次那么Fail一条链都可以匹配，统一计算一下就好惹。

AC自动机：对于所有字符串建立trie树，每个字符串是一条链。之后根据后缀规则建立Fail指针，Fail指针指向的是失配后的最长可用后缀（可以是0）。之后将目标串在自动机上跑就可以了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,c[1000001][26],len[201],num[1000001],res[1000001],fail[1000001],cnt=1;
char s[201][1000000];
int to[1000001],nxt[1000001],head[1000001],tot;
queue<int>q;
inline void AE(int X,int Y){to[++tot]=Y,nxt[tot]=head[X],head[X]=tot;}
void insert(int x)
{
	int pos=1;
	for(int i=1;i<=len[x];++i)
	{
		if(!c[pos][s[x][i]-'a']) c[pos][s[x][i]-'a']=++cnt;
		pos=c[pos][s[x][i]-'a'];
	}
	num[x]=pos;
}
void mkfail()
{
	for(int i=0;i<26;++i) c[0][i]=1;
	q.push(1),fail[1]=0;
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		for(int i=0;i<26;++i) if(c[tmp][i])
		{
			int pos=fail[tmp];
			while(!c[pos][i]) pos=fail[pos];
			fail[c[tmp][i]]=c[pos][i];
			q.push(c[tmp][i]);
		}
	}
}
void match(int x)
{
	int pos=1;
	for(int i=1;i<=len[x];++i)
	{
		while(!c[pos][s[x][i]-'a']) pos=fail[pos];
		res[pos=c[pos][s[x][i]-'a']]++;
	}
}
inline void mktree(){for(int i=1;i<=cnt;++i) AE(fail[i],i);}
void DFS(int pos){for(int i=head[pos];i;i=nxt[i]) DFS(to[i]),res[pos]+=res[to[i]];}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%s",s[i]+1),len[i]=strlen(s[i]+1),insert(i);
	mkfail();
	for(int i=1;i<=n;++i) match(i);
	mktree(),DFS(1);
	for(int i=1;i<=n;++i) printf("%d\n",res[num[i]]);
	return 0;
}