2012-01-18から1日間の記事一覧
問題概要 長さL( 解法 Z-algorithmの練習。 Z-algorithmを適用して、Z[i]=L-iならばsuffixにもなっていることがわかる。後はそれより以前に長さL-i以上の値があったかどうかで判定できる。
ここを読んで勉強した。 コメント読むとKMPと等価とか書かれているけどよく分からない。とりあえずパターンマッチングのO(M+N)が使えるのは良い。 原理の解説も元記事にあるけど、とりあえず入力とパターンマッチングへの応用法だけ書いておく。 長さLの文字…