Spaghetti Sourceの複数パターン検索 (Aho-Corasick)で紹介されているスライドを参考にして、書かれている疑似コードをほぼそのままC++で書き直してみたもの。Trieのvalues_フィールドが保持しているのは、そのノードに到達した時点でマッチしている単語の集…

KMP Algorithm - Search for Problemsに載っているのをちょこちょこ送信中。UVaは掲示板書き込みの英語率が高いのが良い。

長さ1000以下の単語が最大15000個与えられる。最大100*100の文字テーブルの中に出現する単語を全て数え上げよ。文字テーブルの読み方は、縦横斜めをそれぞれ双方向。Aho-Corasick、だけれど、細かい所で注意しないといけない微妙な問題。具体的には以下。 ci…

長さ100000以下の文字列sが与えられる。sの後ろにできるだけ少ない文字列を連結して回文にし、出力せよ。少し考えると、sをreverseした文字列をs_revとして s.substr(s.size() - N) == s_rev.substr(0, N) となるような最大のNを求めれば良い事が分かる（で…