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; }