GCJ 2013 Round1B C.Garbled Email

問題

文字列Sが与えられる。
これは、元の英文からスペースが取り除かれ、いくつかの文字が別の文字に代わってしまっている文で、別な文字に置き換わっているものは、隣接する4文字以下には置き換わっている文字がないことが保障される。
例として、
元の文：code jam
Sの例：codejam, dodejbmなど
Sではありえない例：kodezam(1文字目と5文字目が変化しているが、隣接する4文字以下に置き換わっている文字があるため×)

521196単語の辞書が与えられる。
この辞書を使って、与えられたSの元の英文で文字の置き換わり回数が最小となるような回数は何回かを答える。

small : 20テストケース、1<=Sの長さ<=50
large : 4テストケース、1<=Sの長さ<=4000

考え方

dp。

dp[i][j]:=j文字前が違っている場合の、S[0..i-1]の部分文字列の最小間違い個数
で配るdpする。
dp[i][j]を考えると、S[i]から単語wが並んでいるとすると、j文字前で置き換えが発生しているので、単語wから置き換えが発生しているものが、5-j文字目以降でなければいけない。
もし条件を満たすならば、dp[i+wの長さ][wの長さ-wで最後に置き換えが発生するインデクス]の場所が更新できる。

dp[4001][6]で十分だけど、辞書を探すのに、521196個あるので、単純にやると、
4001*6*521196回計算しないといけない。

辞書の候補となる単語を絞り込むためには、5文字以上置き換え文字が離れている条件を利用して、
「文字S[i]と文字w[0]が同じ単語w」か「文字S[i+1]と文字w[1]が同じ単語w」
を探せばよい。
なので、辞書を読み込むときに1文字目と2文字目について索引インデクスを作っておいて、候補となる文字列をひけば単語を絞り込める。
(でも、書き方の問題もあるけど、largeで5分ぐらいかかる。。。)