TopCoder SRM 519 Div1 Medium RequiredSubstrings

問題

n個の文字列が与えられる。
このうちちょうどC個をその部分文字列として含むような、長さLの文字列の個数を求めよ。

制約条件

n≦6
L≦50

方針

まず、Aho-Corasickでパターンマッチオートマトンを作る。
オートマトンのどの状態にいるか、文字列のうちどれにマッチしたか、長さをキーにしてDPする。
状態遷移はa〜zのアルファベット。

DPの部分が計算量で支配的なので、パターンマッチオートマトンの作成はナイーブにやっても通るらしい。

状態数は50*2^6*50*6くらいで、遷移が26なので計算量的にかなり結構余裕のはず。
なんだけど、最悪で180msとかかかっていてびびる。
mapでlogがかかってるのが遅いのかも。

ソースコード

struct PMA {
  PMA *next[0x100]; // next[0] is for fail
  vector<int> accept;
  PMA() { fill(next, next+0x100, (PMA*)0); }
};
PMA *buildPMA(char p[10][51], int size) {
  PMA *root = new PMA;
  for (int i = 0; i < size; ++i) { // make trie
    PMA *t = root;
    for (int j = 0; p[i][j]; ++j) {
      char c = p[i][j];
      if (t->next[c] == NULL) t->next[c] = new PMA;
      t = t->next[c];
    }
    t->accept.push_back(i);
  }
  queue<PMA*> Q; // make failure link using bfs
  for (int c = 'a'; c <= 'z'; ++c) {
    if (root->next[c]) {
      root->next[c]->next[0] = root;
      Q.push(root->next[c]);
    } else root->next[c] = root;
  }
  while (!Q.empty()) {
    PMA *t = Q.front(); Q.pop();
    for (int c = 'a'; c <= 'z'; ++c) {
      if (t->next[c]) {
        Q.push(t->next[c]);
        PMA *r = t->next[0];
        while (!r->next[c]) r = r->next[0];
        t->next[c]->next[0] = r->next[c];
      	fr(i,r->next[c]->accept)t->next[c]->accept.pb(*i);
      }
    }
  }
  return root;
}
const int mod=9+(int)1e9;
char str[10][51];
int n;
map<pair<int,PMA*>,int > dp[51];

class RequiredSubstrings {
	public:
	int solve(vector <string> words, int C, int L) 
	{
		n=words.size();
		rep(i,n)sprintf(str[i],"%s",words[i].c_str());
		PMA *pma=buildPMA(str,n);
		
		
		rep(i,51)dp[i].clear();
		dp[0][mp(0,pma)]=1;
		rep(i,L)fr(j,dp[i]){
			for(char c='a';c<='z';c++){
				PMA *v=j->first.second;
				int flag=j->first.first;
				while(!v->next[c])v=v->next[0];
				v=v->next[c];
				rep(k,v->accept.size())flag|=1<<v->accept[k];
				(dp[i+1][mp(flag,v)]+=j->second)%=mod;
			}
		}
		
		int ans=0;
		fr(i,dp[L])if(__builtin_popcount(i->first.first)==C)
			(ans+=i->second)%=mod;
		return ans;
	}
};