Codeforces 86 C. Genetic engineering

問題

m個の塩基配列が与えられる。
n文字の塩基配列で、全ての文字が塩基配列にカバーされている
（すべてのiに対して、ある整数l≦i≦rが存在して、塩基配列のl文字目からr文字目までがいずれかの塩基配列に等しい）
ようなものの数をmod 10^9+9で求めよ。

制約条件

n≦1000
m≦10
m個の塩基配列の長さはそれぞれ10以下

方針

Aho-Corasick法でパターンマッチオートマトンを作ってDPする。
dp[pos][(最後に一致したのが何文字前か,オートマトンの状態)]を状態として、
次の文字をA,G,C,Tとして状態を変化させて遷移させる。

最後に一致した文字が10文字以上前だったら、条件が満たされることはないので次の状態を生成する必要はない。

ソースコード

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][11], 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;
}
int match(char *t, PMA *v, int *result) {
  int n = strlen(t);
  int count = 0;
  for (int i = 0; i < n; ++i) {
    char c = t[i];
    while (!v->next[c]) v = v->next[0];
    v = v->next[c];
    for (int j = 0; j < v->accept.size(); ++j)
      result[v->accept[j]]++;
  }
}
const int mod=(int)1e9+9;
int n,m;
map<pair<int,PMA*>,int> dp[2];
int len[10];
char in[10][11];
const char *base="ACGT";

void run(){
  cin>>n>>m;
  rep(i,m){
    cin>>in[i];
    len[i]=strlen(in[i]);
  }
  PMA* pma=buildPMA(in,m);
  dp[0][mp(0,pma)]=1;
  int cur=0,next=1;
  rep(i,n){
    dp[next].clear();
    fr(it,dp[cur]){
      rep(b,4){
        PMA *v=it->first.second;
        while(!v->next[base[b]])v=v->next[0];
        v=v->next[base[b]];
        int mxlen=-1;
        fr(jt,v->accept)mxlen=max(mxlen,len[*jt]);
        
        if(it->first.first<mxlen)(dp[next][mp(0,v)]+=it->second)%=mod;
        else if(it->first.first+1<12) (dp[next][mp(it->first.first+1,v)]+=it->second)%=mod;
      }
    }
    swap(cur,next);
  }
  
  int ans=0;
  fr(i,dp[cur])if(i->first.first==0)ans=(ans+i->second)%mod;
  cout<<ans<<endl;
}