POJ 1432 Decoding Morse Sequences

問題

モールス信号が与えられる。
この信号は、すべて辞書の単語をモールス信号に変換したものを並べたものである。


モールス信号の解釈の仕方は何通りあるか、出力せよ。
ただし、モールス信号を解釈した際に過不足があってはならない。

制約条件

データセットの個数≦20
モールス信号の長さ≦10000
単語の数≦10000

方針

ややTLEが怪しい方針しか立たなかった。
本当はパターンマッチオートマトンを使ったDPをやる気がする。
自分の方針は以下の通り。


dp[i]を、モールス信号のi文字目までを文字列として解釈した時の場合の数とする。
全ての単語jについて、モールス信号のi+1文字目からi+len[j]文字目までが単語jに等しいとき、
dp[i+len[j]] += dp[i]が成り立つ。


全てのi,jに対してこの漸化式をまわすDPにより場合の数が求まる。
文字のマッチングの部分は愚直にやるとO(文字列長)の時間がかかるが、
ローリングハッシュを使うことでO(1)の時間でできる。

ソースコード

int n, m, len[10000];
char in[10001], word[21];
int dp[10001];

ll hash[10001], whash[10000];
const char *morse[]={
  ".-","-...","-.-.","-..",
  ".","..-.","--.","....",
  "..",".---","-.-",".-..",
  "--","-.","---",".--.",
  "--.-",".-.","...","-",
  "..-","...-",".--","-..-",
  "-.--","--.."};
  
int main(){
  int d; scanf("%d ",&d);
  while(d--){
    gets(in);
    m=strlen(in);
    scanf("%d ",&n);
    rep(i,n){
      gets(word);
      string tmp;
      for(int j=0;word[j];j++)tmp+=morse[word[j]-'A'];
      
      len[i]=tmp.size();
      whash[i]=0;
      for(int j=len[i]-1;j>=0;j--)whash[i]*=3, whash[i]+=(tmp[j]=='-'?2:1);
    }
    ll base=1;
    rep(i,m){
      hash[i+1]=hash[i]+base*(in[i]=='-'?2:1);
      base*=3;
    }
    
    rep(i,m+1)dp[i]=0;
    dp[0]=1;
    base=1;
    rep(i,m){
      rep(j,n)if(i+len[j]<=m){
        if(hash[i+len[j]]-hash[i]==whash[j]*base)dp[i+len[j]]+=dp[i];
      }
      base*=3;
    }
    printf("%d\n",dp[m]);
  }
  return 0;
}