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を求めれば良い事が分かる（で…

二部マッチングの練習をしようと思ったら丸一日かかった…グラフはこんな感じ。 SRC --1-- CANDIDATE(i) --1-- PROJECT(j) --r-- SINKまず最初にここと同じで、一人目の一つ目の仕事からgreedyに割り振り、流量が減らないなら採用する事を繰り返す、という方…

こんなのが紹介されていたのでメモ。

UVa 563 Crimewave50*50の格子点上に泥棒が沢山居て、他の泥棒の逃走経路と交差しないような逃走経路で格子点から逃げ出したい（格子点の端の点に辿り着けば良い）。全ての泥棒がそのようにして逃走可能ならばpossible、不可能ならばnot possibleと出力せよ…