POJ 1732 Phone numbers

問題

アルファベットに数字が対応している。

	1 ij	2 abc	3 def

	4 gh	5 kl	6 mn

	7 prs	8 tuv	9 wxy

		0 oqz

文字列からなる辞書が与えられる。
数字の列が与えられたとき、数字の列を文字列として解釈せよ。
解釈の仕方が複数通りある場合、単語数が最も少ないものを出力せよ。

制約条件

辞書の単語数≦50000
数字の長さ≦100
辞書の各単語の長さ≦50

方針

Aho-Crosick法でパターンマッチオートマトンを作ってDPする。
dp[i]を、i文字目までが辞書の文字列に完全にマッチするときの、単語の数の最小値である。

ソースコード

spaghetti sourceのAho-Crosickは間違っていたので修正した。

int n, len;
char in[101], word[50000][51], num[50000][51];

struct PMA {
  PMA *next[0x100]; // next[0] is for fail
  vector<int> accept;
  PMA() { fill(next, next+0x100, (PMA*)0); }
};
PMA *buildPMA(char p[50000][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 = '0'; c <= '9'; ++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 = '0'; c <= '9'; ++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); //fixed
      }
    }
  }
  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]]++;
  }
}

int dp[101], prev[101];
int l[50000], ans[100], sz;
char cnv[256];

int main(){

  const char *tmp="oqzij*abcdefgh*kl*mn*prstuvwxy";
  rep(i,30)cnv[tmp[i]]='0'+i/3;

  scanf("%s",in);
  len=strlen(in);
  
  scanf("%d ",&n);
  rep(i,n){
    scanf("%s",word[i]);
    l[i]=strlen(word[i]);
    rep(j,l[i])num[i][j]=cnv[word[i][j]];
  }
  
  PMA *v=buildPMA(num,n);
  
  rep(i,len+1)dp[i]=(int)1e9;
  dp[0]=0;
  rep(i,len){
    char c=in[i];
    while(!v->next[c]){
      v=v->next[0];
    }
    v=v->next[c];
    rep(j,v->accept.size())
    if(i-l[v->accept[j]]+1>=0&&dp[i+1]>dp[i-l[v->accept[j]]+1]+1){
      dp[i+1]=dp[i-l[v->accept[j]]+1]+1;
      prev[i+1]=v->accept[j];
    }
  }
  if(dp[len]==(int)1e9){
    puts("No solution."); return 0;
  }
  
  for(int i=len;i;i-=l[prev[i]])ans[sz++]=prev[i];
  reverse(ans,ans+sz);
  rep(i,sz)printf("%s%c",word[ans[i]],i==sz-1?'\n':' ');
  
  return 0;
}