2257-Sakura Poetry

問題文

解法

解説通りのDP
AOJで通すにはmapを用いてメモリ利用量を減らす必要がある．

実装(C++)

メモリ管理がダメダメです．

#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
using namespace std;
#define REP(i,x) for(int i=0;i<(int)x;i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
struct PMA{
	PMA* next[256]; //失敗時に0を利用
	int matched;
	int v; //Debug
	PMA(){REP(i,256)next[i]=0;matched=false;}
	~PMA(){REP(i,256)if(next[i])delete next[i];}
};
PMA* pmas[5000];
int pma_count=1;
//パターンマッチングオートマトンの生成．生成元パターンをpattern,個数をcountに代入して用いる
PMA *buildPMA(string pattern[],int count){
	PMA *root=new PMA,*now;
	root->next[0]=root;
	root->v=0;
	REP(i,count){
		now=root;
		for(int j=0;j<(int)pattern[i].size();j++){
			if(now->next[(int)pattern[i][j]]==0){
				now->next[(int)pattern[i][j]]=new PMA;
				now->next[(int)pattern[i][j]]->v=pma_count;
				pmas[pma_count++]=now->next[(int)pattern[i][j]];
			}
			now=now->next[(int)pattern[i][j]];
		}
		now->matched+=1;
	}

	queue<PMA*> que;
	for(int i=1;i<256;i++){
		if(!root->next[i])root->next[i]=root; //使われていない部分のnextをrootに
		else{
			root->next[i]->next[0] = root; //失敗時はルートに戻る
			que.push(root->next[i]);
		}
	}
	while(!que.empty()){
		now=que.front();que.pop();
		for(int i=1;i<256;i++){
			if(now->next[i]){
				PMA *next=now->next[0];
				while(!next->next[i])next=next->next[0];
				now->next[i]->next[0]=next->next[i];
				now->next[i]->matched+=(next->next[i]->matched);
				que.push(now->next[i]);
			}
		}
	}
	return root;
}

int match(PMA* &pma,const string &a){
	int res=0;
	FOR(it,a){
		int c=*it;
		while(!pma->next[c]){
			pma=pma->next[0];
		}
		pma=pma->next[c];
		res+=pma->matched;
	}
	return res;
}

int n,m,k;
string seasonword[30];
vector<string> words;
int wc;
vector<int> G[1000];
int fromstring(string &a){
	int k=find(words.begin(),words.end(),a)-words.begin();
	if(k==(int)words.size()){
		words.push_back(a);wc++;
	}
	return k;
}
const int MOD=1000000007;
//長さ．えいほこらしっく，さいごのたんご，きごのかず
struct State{
	int aho;
	int lastword;
	int count;
};
bool operator<(const State &a,const State &b){
	return a.aho==b.aho?a.lastword==b.lastword?a.count<b.count:a.lastword<b.lastword:a.aho<b.aho;
}
map<State,int> dp[30];
int main(){
	for(;cin>>n>>m>>k;){
		if(!(n|m|k))break;
		wc=0;words.clear();
		REP(i,900)G[i].clear();
		REP(i,n){
			string a,b;
			cin>>a>>b;
			int a_=fromstring(a),b_=fromstring(b);
			G[a_].push_back(b_);
		}
		REP(i,k)
			cin>>seasonword[i];
		pma_count=1;
		pmas[0]=buildPMA(seasonword,k);
		REP(i,30)dp[i].clear();
		swap(n,m);
		REP(i,wc){
			PMA *next=pmas[0];
			int MA=match(next,words[i]);
			if(MA<2)dp[words[i].size()][(State){next->v,i,MA}]=1;
		}
		REP(i,n){
			dp[(i+25)%30].clear();
			FOR(it,dp[i%30]){
				REP(q,G[it->first.lastword].size()){
					int n_k=G[it->first.lastword][q];
					if(i+(int)words[n_k].size()>n)continue;
					PMA *next=pmas[it->first.aho];
					int MA=it->first.count+match(next,words[n_k]);
					if(MA<2){
						dp[(i+words[n_k].size())%30][(State){next->v,n_k,MA}]+=it->second;
						dp[(i+words[n_k].size())%30][(State){next->v,n_k,MA}]%=MOD;
					}
				}
			}
		}
		int res=0;
		FOR(it,dp[n%30]){
			if(it->first.count==1){
				res+=it->second;
				res%=MOD;
			}
		}
		cout<<res<<endl;
	}
	return 0;
}