snuke.hatenablog.com
上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。
KMPは、上の記事で紹介したMP（Morris-Pratt）にKnuthパワーが加わったものです。
さらなる考察がされて、文字列検索の効率が向上した感じです。
計算量的な面でも、全体計算量は線形のままですが、後述するような嬉しい点があります。
復習+α
まずはMPの復習からです。
上の記事で求めている A は 最長border と呼ばれるものらしいです。
文字列 S "aabaabaa" の A(border) は -1,0,1,0,1,2,3,4,5 となります。
この文字列の末尾にもう１文字加えたとき、A[9] はどう計算すればいいでしょうか？
図の赤い矢印は i→A[i] を結んでいます。
A[9] を求めるステップは以下のとおりです。
- 赤い矢印を辿って、次の文字を見る。
- ? と一致していたらそこの次の位置が A[9] になる。
- 異なるなら、また赤い矢印を辿って・・・を続ける。
? が a,b,c のときについてそれぞれ実際にシミュレートしてみるとイメージが湧きやすいかもしれません。
さて、ここまでがMPですが、MPの計算量は均し計算量でO(1)です。
つまり、１ステップの計算量は最悪でO(N)になることもあります。
例えば、aaa...aaab について計算する時、b を追加したときには赤い矢印を a の個数回辿らなければなりません。
KMP
下図のような青い矢印を考えます。
この青い矢印は「"次の文字"が異なるまで赤矢印を辿った場所」に張られたものです。
実は先程の A[9] を求めるステップでは、青矢印を赤矢印の代わりに使っても正しい答えが求まります。
なぜなら、5→2 の矢印をたどるということは ? が b ではなかったということで、それなら 2 を試す必要はなくスキップしても同じで、同様に 1→0 の矢印もスキップして良いからです。
実はこれで１ステップの計算量をO(log N)で抑えることができます。
で、これがKMPのKです。
計算量を解析してみます。間違っていたので修正しました（2022-09-15）
ある場所から赤矢印を辿るときの「"次の文字"が異なる赤矢印」（特別な赤矢印と呼ぶことにする）の個数を見積もればよいです。
赤矢印を辿って α → β → γ と遷移し、２つ目の矢印が特別な赤矢印であるとき、
が成り立つことを示します。
と仮定すると、
- β は α のprefixかつsuffix
- γ は β のprefixかつsuffixなので α のsuffixでもある
- α の |β|+1 文字目を x、|γ|+1 文字目を y とすると x ≠ y (∵２つ目の矢印は特別な赤矢印)
- γ の d+1 文字目は x、β の d+1 文字目は y であり、γ が β のprefixであることに矛盾する ■
特別な赤矢印を辿る回数が k 回になるような最短の文字列の長さを 
とすると、
（上の状況で α→β は特別な赤矢印とは限らないが、βの前に辿った最後の特別な赤矢印の直前の文字列の長さは |α| 以上）
L を帰納的に求めるとfibonacci数的になっているため、特別な赤矢印を辿る回数は O(log N) 回であることが示せる。ちなみに log の底は黄金比 φ = 
で、最悪ケースは fibonacci word。
実装等はこの記事を参考にするといいでしょう。ここも良さそう。
応用問題
xmas contest 2015 D - Destroy the Duplicated Poem
問題概要を一口で説明すると「Trie木が与えられるので各頂点に対して赤矢印を求めよ」です。
普通にMPをやろうとすると、aaa...aaときてそのあとにbやらcやらと枝分かれしまくるケースとかで計算量が２乗に爆発してしまいます。
そこで、KMPを使えば遷移が常にO(log N)で抑えられてしまいます。やったー。
ソースコード
木上でやるとなると少し実装がトリッキーになるので頑張って混乱しないように整理して実装しましょう。
ちなみに想定解は違う解法だったので、期せずしてKMPの良い例題を作ってしまったらしい。
