[bzoj1030]-[JSOI2007]文本生成器

题目（BZOJ）
题目（洛谷）
AC自动机+dp，没毛病。
dp[i][j]表示匹配到第i位时，目前在自动机上第j号点的路径数，
然后来个补集转化，完毕。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <climits>
#include <cctype>
#include <cstdlib>
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char chh=getchar();
	while(!isdigit(chh)){if(chh=='-')ck=1;chh=getchar();}
	while(isdigit(chh)){e=(e<<1)+(e<<3)+(chh^48);chh=getchar();}
	if(ck)e=-e;
}
const int mod=10007;
int n,m,sum=1,ans,dp[150][7005],tmp;
int q[7050];
struct ACmata{
	int ch[7005][30];
	int fail[7005],match[7005];
	int sz;
	void init(){
		sz=1;
		memset(ch,0,sizeof ch);
		memset(fail,0,sizeof fail);
		memset(match,0,sizeof match);
		for(int i=1;i<=26;++i)ch[0][i]=1;
	}
	inline int idx(char cc){return cc-'A'+1;}
	inline void ins(char *s){
		int r=1,len=strlen(s);
		for (int i=0;i<len;++i){
			int c=idx(s[i]);
			if(ch[r][c])r=ch[r][c];
			else r=ch[r][c]=++sz;
		}
		match[r]=1;
	}
	inline void getfail(){
		int head=0,tail=1;
		fail[1]=0;q[0]=1;
		while(head<tail){
			int r=q[head++];
			for (int c=1;c<=26;c++){
				if(!ch[r][c])continue;
				int v=fail[r];
				while(!ch[v][c])v=fail[v];
				fail[ch[r][c]]=ch[v][c];
				match[ch[r][c]]|=match[ch[v][c]];
				q[tail++]=ch[r][c];
			}
		}
	}
}ac;
char ss[150];
int main(){
	scanf(
	ac.init();
	for (int i=1;i<=m;++i) sum*=26,su
	for (int i=1;i<=n;++i){
		scanf(
		ac.ins(ss);
	}
	ac.getfail();
	dp[0][1]=1;
	for (int i=1;i<=m;++i){
		for (int j=1;j<=ac.sz;++j){
			if (ac.match[j]||!dp[i-1][j])continue;
			for (int k=1;k<=26;++k){
				int u=j;
				while(!ac.ch[u][k])u=ac.fail[u];
				dp[i][ac.ch[u][k]]+=dp[i-1][j];
				dp[i][ac.ch[u][k]
			}
		}
	}
	for (int i=1;i<=ac.sz;++i)if(!ac.match[i])tmp+=dp[m][i],tm
	printf(
	return 0;
}