POJ 3073 Spam

問題

アルファベットを暗号に変換する変換表が与えられる。
文字列が与えられる。これを暗号に変換し、復号するとき、何通りの文字列に復号できるか答えよ。

制約条件

入力のサイズ≦100

方針

Aho-Corasck法でパターンマッチオートマトンを作ってDPする。
POJ3600とほぼ同じ。

DP[i]をi文字目まで完全にマッチするような場合の数として、
それをオートマトンを使い更新するようなDPをすればいい。

ソースコード

struct PMA {
  PMA *next[0x100]; // next[0] is for fail
  vector<int> accept;
  PMA() { fill(next, next+0x100, (PMA*)0); }
};
PMA *buildPMA(const char *p[], 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 = 35; c <= 124; ++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 = 35; c <= 124; ++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 char *spam[]={
"4","|3","(","|)","3","|=","6","#","|","_|","|<","|_","|\\/|",
"|\\|","0","|0","(,)","|?","5","7","|_|","\\/","\\/\\/","><","-/","2"};
int l[26];

char in[101];

int dp[1000];
int solve(PMA *p){
  
  string str;
  for(int i=0;in[i];i++)str+=spam[in[i]-'A'];
  int len=str.size();
  
  rep(i,len)dp[i+1]=0;
  dp[0]=1;
  rep(i,len){
    char c=str[i];
    while(!p->next[c])p=p->next[0];
    p=p->next[c];
    rep(j,p->accept.size())
      dp[i+1]+=dp[i+1-l[p->accept[j]]];
  }
  return dp[len];
}

int main(){
  rep(i,26)l[i]=strlen(spam[i]);
  PMA *p = buildPMA(spam, 26);
  
  while(scanf("%s",in),in[0]!='e')
    printf("%d\n",solve(p));
  return 0;
}