BZOJ 1030 JSOI2007 文本生成器 AC自动机+DP

题目大意：给定n个模式串，求长度为m的至少含有一个模式串的字符串共有多少种

照例，令f[i][j]表示长度为i的字符串与AC自动机上的第j个点匹配的方案数

直接DP很难，我们考虑补集法，即用26^m减去不含任何模式串的字符串的数量

后者就是经典的AC自动机DP模型啦~~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD 10007
using namespace std;
struct Trie{
	Trie *son[26],*fail;
	bool ed;
}*root,mempool[6060],*C=mempool;
int n,m,ans;
int f[110][6060];
char s[110];
void Insert(Trie* &p,char *s)
{
	if(!p) p=C++;
	if(!*s)
	{
		p->ed=1;
		return ;
	}
	Insert(p->son[(*s)-'A'],s+1);
}
void Build_Tree()
{
	static Trie *q[6060];
	static int r,h;
	int i;
	for(i=0;i<26;i++)
		if(root->son[i])
			root->son[i]->fail=root,q[++r]=root->son[i];
		else
			root->son[i]=root;
	while(r!=h)
	{
		Trie *p=q[++h];
		for(i=0;i<26;i++)
			if(p->son[i])
			{
				p->son[i]->fail=p->fail->son[i];
                p->son[i]->ed|=p->son[i]->fail->ed;
                q[++r]=p->son[i];
			}
			else
				p->son[i]=p->fail->son[i];
	}
}
int Quick_Power(int x,int y)
{
	int re=1;
	while(y)
	{
		if(y&1) re*=x,re%=MOD;
		x*=x,x%=MOD;
		y>>=1;
	}
	return re;
}
int main()
{
	int i,j,k;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		scanf("%s",s),Insert(root,s);
	Build_Tree();
	f[0][0]=1;
	for(i=0;i<m;i++)
		for(j=0;j<C-mempool;j++)
			if(!mempool[j].ed)
				for(k=0;k<26;k++)
					f[i+1][mempool[j].son[k]-mempool]+=f[i][j],
					f[i+1][mempool[j].son[k]-mempool]%=MOD;
	ans=Quick_Power(26,m);
	for(j=0;j<C-mempool;j++)
		if(!mempool[j].ed)
			ans+=MOD-f[m][j],ans%=MOD;
	cout<<ans<<endl;
	return 0;
}
//f[i][j]表示第i个字符对应AC自动机上的第j个节点且不含任何模式串的方案数