Codeforces Round #362 (Div. 1) D. Legen...
http://codeforces.com/contest/696/problem/D
解法
この問題は蟻本の p.327「禁止文字列」と p.329「DNA Repair」のように、パターンマッチングオートマトン上の DP が可能である。今回は複数文字列なので、DNA Repair の方が近い。
DP テーブルは次の通り。
- dp[ 確定した文字長 ][ オートマトンの状態 ] := 最大スコア
求めたいのは dp[L][*] であるが、L が大きいため愚直な DP では間に合わない。といっても高速化するのは難しくなくて、積を +、和を max とした代数系で行列累乗すればいい。
難しいのはどのようにオートマトンを構成するのかという部分。
単一文字列の場合は各文字を状態に、複数文字列の場合は Trie のノードを状態にすればいいのは大体分かる。 問題なのは遷移関数の作り方だろう。
状態 q から文字 c でどこに遷移すれば良いのかというと、次のようにすればいい。
- Trie 上の辺があるならそれに沿って遷移する
- Trie 上の辺がないなら、現在の状態に対応する文字列の先頭を一文字ずつ削っていき、Trie 上の辺が見つかったらそれに沿って遷移する
遷移の張り方は spagetti source で紹介されていた
http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
が分かりやすかった。
蟻本では本当に先頭を一文字ずつ削っているが、Aho-Corasick 法の場合は fail という遷移を使うことで高速化している。
今回は総文字列長が小さいので愚直に処理できる。
一応 Aho-Corasick 法も書いておいた。