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[L][*] であるが、L が大きいため愚直な DP では間に合わない。といっても高速化するのは難しくなくて、積を +、和を max とした代数系で行列累乗すればいい。

難しいのはどのようにオートマトンを構成するのかという部分。

単一文字列の場合は各文字を状態に、複数文字列の場合は Trie のノードを状態にすればいいのは大体分かる。 問題なのは遷移関数の作り方だろう。

状態 q から文字 c でどこに遷移すれば良いのかというと、次のようにすればいい。

  1. Trie 上の辺があるならそれに沿って遷移する
  2. Trie 上の辺がないなら、現在の状態に対応する文字列の先頭を一文字ずつ削っていき、Trie 上の辺が見つかったらそれに沿って遷移する

遷移の張り方は spagetti source で紹介されていた http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
が分かりやすかった。

蟻本では本当に先頭を一文字ずつ削っているが、Aho-Corasick 法の場合は fail という遷移を使うことで高速化している。


今回は総文字列長が小さいので愚直に処理できる。

一応 Aho-Corasick 法も書いておいた。

gist.github.com

単一文字列ならオートマトンが作れるのは知っていたので、複数文字列でも作れるだろうとは思ったが自力では無理だった。文字列系アルゴリズムの知識が浅い。