AOJ 2257: Sakura Poetry

Aho-Corasick + DP + メモリの定数倍
kuso....

#include<stdio.h>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;
long long mod=1000000007;
char in[30];
string table[600];
vector<int>g[600];
struct wolf{
	int chi[26];
	int mark;
	int par;
	int fail;
	int var;
	wolf(){
		for(int i=0;i<26;i++)chi[i]=-1;mark=0;
		par=fail=var=-1;
	}
};
wolf node[700];
int ns;
void add(){
	int at=0;
	for(int i=0;in[i];i++){
		if(node[at].chi[in[i]-'a']==-1){
			node[at].chi[in[i]-'a']=ns;
			node[ns].par=at;
			node[ns].var=in[i]-'a';
			at=ns++;
		}else{
			at=node[at].chi[in[i]-'a'];
		}
	}
	node[at].mark++;
}
int n;
vector<int>dp[2][520][520];
int conv[520][700];
int cs[520];
int calc(int a,int b,int c,int d){
//	if(c&&conv[b][c]==0)printf("%d %d %d\n",b,c,conv[b][c]);
	if(~dp[d][a][b][conv[b][c]])return dp[d][a][b][conv[b][c]];
	if(a==n){
		if(d==1)return 1;
		else return 0;
	}
	int ret=0;
	for(int i=0;i<g[b].size();i++){
		int to=c;
		int cnt=d;
		int use=g[b][i];
		if(a+table[use].size()>n)continue;
		for(int j=0;j<table[use].size();j++){
			while(1){
				if(node[to].chi[table[use][j]-'a']!=-1){
					to=node[to].chi[table[use][j]-'a'];
					break;
				}
				if(to==0)break;
				to=node[to].fail;
			}
			cnt+=node[to].mark;
		}
		if(cnt>1)continue;
		ret=(ret+calc(a+table[use].size(),use,to,cnt))%mod;
	}
	//if(ret)printf("%d %d %d %d: %d\n",a,b,c,d,ret);
	return dp[d][a][b][conv[b][c]]=ret;
}
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),a){
		n=b;
		map<string,int> word;
		for(int i=0;i<600;i++)g[i].clear();
		for(int k=0;k<2;k++)for(int i=0;i<520;i++)for(int j=0;j<520;j++)dp[k][i][j].clear();
		for(int i=0;i<520;i++)cs[i]=0;
		int sz=0;
		for(int i=0;i<a;i++){
			int P,Q2;
			scanf("%s",in);
			string p=in;
			if(word.count(p))P=word[p];
			else{
				word[p]=sz;
				table[sz]=p;
				P=sz++;
			}
			scanf("%s",in);
			string q=in;
			if(word.count(q))Q2=word[q];
			else{
				word[q]=sz;
				table[sz]=q;
				Q2=sz++;
			}
			g[P].push_back(Q2);
		}
		for(int i=0;i<600;i++)node[i]=wolf();
		ns=1;
		for(int i=0;i<c;i++){
			scanf("%s",in);
			add();
		}
		queue<int>Q;
		Q.push(0);
		while(Q.size()){
			int at=Q.front();Q.pop();
			if(at==0||node[at].par==0)node[at].fail=0;
			else{
				int to=node[at].par;
				while(1){
					int tmp=node[to].fail;
					if(node[tmp].chi[node[at].var]!=-1){
						node[at].fail=node[tmp].chi[node[at].var];
						node[at].mark+=node[node[at].fail].mark;
						break;
					}
					to=tmp;
					if(to==0){node[at].fail=0;break;}
				}
			}
			for(int i=0;i<26;i++)if(node[at].chi[i]!=-1){
				Q.push(node[at].chi[i]);
			}
		}
	//	printf("%d\n",ns);
		for(int i=0;i<sz;i++){
			for(int j=0;j<ns;j++){
				bool ok=true;
				int at=j;
				int in=table[i].size()-1;
				while(at&&in>=0){
					if(node[at].var!=table[i][in]-'a'){ok=false;break;}
					at=node[at].par;
					in--;
				}
				if(ok){
					conv[i][j]=cs[i]++;
				}
			}
		}
		//for(int i=0;i<sz;i++)printf("%d\n",cs[i]);
		conv[sz][0]=0;cs[sz]=1;
		for(int i=0;i<2;i++)for(int j=0;j<=b;j++)for(int k=0;k<=sz;k++){
			dp[i][j][k]=vector<int>(cs[k],-1);
		}
		for(int i=0;i<sz;i++)g[sz].push_back(i);
		int ret=calc(0,sz,0,0);
		
		printf("%d\n",ret);
	}
}