Codeforces Manthan, Codefest 16 C. Spy Syndrome 2

制約が怖すぎる。

次のような DP をしたあとで復元する。

S[i..j] が単語のリストにあれば dp[i] から dp[j+1] に遷移できる。状態数が 10000、遷移数が 1000 なので厳しそうだけど通る。

多項式ハッシュを使えば単語リストにあるかの判定をO(1) あるいは O(log n) でできる。ただし最大単語数が 10⁵ 個なので一種類のハッシュでは高確率でハッシュが衝突することに注意する必要がある（誕生日のパラドックス）。

ハッシュの計算がおかしかったので衝突や TLE 以前に WA だった。それにしても制約が厳しい。