空き缶ACオートマチック+DP好題

リンク:http://zerojudge.tw/ShowProblem?problemid=b179
この問題をするにはまずacオートマチックを理解しなければなりません!!
いい問題ですね.毎日文字列が末尾に1つ拡張されるほか、先頭の文字が消えて長さが短くなります.最後にn日間の時間内に何個の列が消え、何個の列が病気で入院したかを統計する(ウイルス列を含む)
この状態を説明するには、数日が経過したことを考慮する必要があります. 列の長さはいくらですか. どのノードにとどまるかは、一般的にオートマチックdpがそうですが、肝心なのはどのように移行するかです.
まず末尾に1文字拡張しますが、これは一般的なオートマチックDPにある遷移です.
頭から文字を削除するのはちょっといいですね
3つの状況に分ける.
1:列の長さが1の場合、削除すると消えてしまいます.その場合は現在の状態を加算します
2:列の長さはちょうどノードにとどまる深さであり,長さが1つ減った後は現在のノードにとどまることができないが,どこへ行くのか.明らかにfailポインタ!
3:列の長さはこのノードの深さより大きく、それは間違いなく長さが1つ減少し、現在のノードにとどまる.
現在のノードの深さよりも小さい長さは不正です.考慮する必要はありません.
もう一つの注意点は、1次元がスクロール配列を使うことです.スクロールするときは空にすることを忘れないでください.
一度間違えて配列が小さくなった.
デバッグを支援するデータのセット
a 3 3 ab cc dd 4 14

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int M = 1510;
const int CD = 4;
int ID[128];;
int ch[M][CD];
int Q[M];
int fail[M];
int sz;
int val[M];
void Init(){
	sz=1;
	memset(ch[0],0,sizeof(ch[0]));
	fail[0]=0;  val[0]=0;
	ID['a']=0; ID['b']=1;ID['c']=2;ID['d']=3;
}
int dep[M];
void Insert(char *s) {
	int p=0; int d=0;
	for(;*s;s++) {
		d++;
		int c=ID[*s];
		if(!ch[p][c]) {
			memset(ch[sz],0,sizeof(ch[sz]));
			val[sz]=0;
			dep[sz]=d;
			ch[p][c]=sz++;
		}
		p=ch[p][c];
	}
	val[p]=1;
}
void Construct() {
	int *s=Q,*e=Q;
	for(int i=0;i<CD;i++) {
		if(ch[0][i]) {
			fail[ch[0][i]] = 0;
			*e++ = ch[0][i];
		}
	}
	while(s!=e) {
		int u = *s++;
		for(int i=0;i<CD;i++) {
			int &v = ch[u][i];
			if(v) {
				*e++ = v;
				fail[v] = ch[fail[u]][i];
				val[v] |= val[fail[v]];
			} else {
				v = ch[fail[u]][i];
			}
		}
	}
}
const int mod = 10007;
char str[110];
int dp[2][110][1510];
bool init(char *s)
{
	memset(dp,0,sizeof(dp));
	int p=0,len=0;
	for(;*s;s++) 
	{
		len++;
		int c=ID[*s];
		p=ch[p][c];
	}
	dp[0][len][p]=1;
	if(val[p])return false;
	return true;
}
void solve(int n)
{
	bool flag=init(str);
    if(!flag) {
		puts("0 1
");return ;
	}
	int x=0,ans=0,ret=0;
	for(int i=0;i<n;i++)
	{
		x^=1;
		for(int y=1;y<=100;y++)	memset(dp[x][y],0,sizeof(dp[x][y]));
		for(int j=0;j<sz;j++)if(!val[j])
		{
			for(int len=1;len<=100;len++) if(dp[x^1][len][j])//    len    j  
			{
				if(len == 1) {
					ans=(ans+dp[x^1][len][j])%mod;
				} else if(len==dep[j]) {
					dp[x][len-1][fail[j]] += dp[x^1][len][j];
					dp[x][len-1][fail[j]] %= mod;
				} else if(len>dep[j]){
					dp[x][len-1][j] += dp[x^1][len][j];
					dp[x][len-1][j] %= mod;
				}
				for(int k=0;k<4;k++) {
					int to=ch[j][k];
					dp[x][len+1][to] += dp[x^1][len][j];
					dp[x][len+1][to] %= mod;
					if(val[to]) {
						ret=(ret+dp[x^1][len][j])%mod;
					}
				}
			}
		}
	}
	printf("%d %d
",ans,ret);
}
int main(){
	char s[110];
	Init();
	scanf("%s",str);
	int n,p;
	scanf("%d%d",&n,&p);
	for(int i=0;i<p;i++)
	{
		scanf("%s",s);
		Insert(s);
	}
	Construct();
	solve(n);
	return 0;
}
/*
a
3
3
ab
cc
dd

4 14
*/