Ryan_<

妨碍我们学习的不是未知的，而是已知的，尤其是那种略知一二的。

//发现自己原来什么都不会。

Trie图！=AC自动机=Trie树+Fail指针

我们建的一般都是Trie图，而利用Fail指针组成的树来解题。

BZOJ1030 JSOI2007 文本生成器

很经典的题。1A

const int M=100+10,N=6000+10;
int n,m,tot=1,ans;//注意!! 
char s[M];
int val[N],t[N][27],f[N],dp[M][N];
void insert()
{
	scanf("%s",s+1);
	int len=strlen(s+1);
	int now=1;
	F(i,1,len){
		int x=s[i]-'A'+1;
		if(!t[now][x]) t[now][x]=++tot;
		now=t[now][x];
	}
	val[now]=1;
}
void bfs()
{
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();
//		int j=f[x];
		F(i,1,26){
			int j=f[x];
			while(j && !t[j][i]) j=f[j];
			if(t[x][i]){
				int y=t[x][i];
				f[y]=j?t[j][i]:1;
				val[y]=val[y]|val[f[y]];
				q.push(y);
			}
			else t[x][i]=j?t[j][i]:1;
		}
	}
}
void Dp()
{
	mec(dp,0);dp[0][1]=1;ans=1;
	F(i,0,m-1) {
		F(j,1,tot) {
			if(val[j]||!dp[i][j]) continue; 
			F(k,1,26)
				dp[i+1][t[j][k]]=(dp[i+1][t[j][k]]+dp[i][j])%MOD;
		}	
		ans=ans*26%MOD;
	}
	F(i,1,tot) if(!val[i])
		ans=(ans-dp[m][i]+MOD)%MOD;
}
/*****main******/
F(i,1,n) insert();
bfs();
Dp();

BZOJ3172 TJOI2013 单词

（中午发现了一件奇妙的事情，就跑来写一发> _ <

这道题只要考虑Fail树就好！每个串出现的次数=以该串结束结点为根的Fail树大小

怎么求大小？树中的问题我们通常dfs一遍，而这里我们已经有了bfs序！

沿着Fail能够到达该节点的点一定在它之后bfs!

按照bfs逆序执行cnt[fail[i]]+=cnt[i]统计答案即可