KMPのK

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 となります。
この文字列の末尾にもう1文字加えたとき、A[9] はどう計算すればいいでしょうか?

図の赤い矢印は i→A[i] を結んでいます。
A[9] を求めるステップは以下のとおりです。

  1. 赤い矢印を辿って、次の文字を見る。
  2. ? と一致していたらそこの次の位置が A[9] になる。
  3. 異なるなら、また赤い矢印を辿って・・・を続ける。

? が a,b,c のときについてそれぞれ実際にシミュレートしてみるとイメージが湧きやすいかもしれません。

さて、ここまでがMPですが、MPの計算量は均し計算量でO(1)です。
つまり、1ステップの計算量は最悪でO(N)になることもあります。
例えば、aaa...aaab について計算する時、b を追加したときには赤い矢印を a の個数回辿らなければなりません。

KMP

下図のような青い矢印を考えます。
この青い矢印は「"次の文字"が異なるまで赤矢印を辿った場所」に張られたものです。

実は先程の A[9] を求めるステップでは、青矢印を赤矢印の代わりに使っても正しい答えが求まります。
なぜなら、5→2 の矢印をたどるということは ? が b ではなかったということで、それなら 2 を試す必要はなくスキップしても同じで、同様に 1→0 の矢印もスキップして良いからです。

実はこれで1ステップの計算量をO(log N)で抑えることができます。
で、これがKMPのKです。
計算量を解析してみます。間違っていたので修正しました(2022-09-15)

ある場所から赤矢印を辿るときの「"次の文字"が異なる赤矢印」(特別な赤矢印と呼ぶことにする)の個数を見積もればよいです。

赤矢印を辿って α → β → γ と遷移し、2つ目の矢印が特別な赤矢印であるとき、

  •  |α| \gt |β|+|γ|

が成り立つことを示します。 0 \leq |β|+|γ|-|α| (= d) と仮定すると、

  • β は α のprefixかつsuffix
  • γ は β のprefixかつsuffixなので α のsuffixでもある
  • α の |β|+1 文字目を x、|γ|+1 文字目を y とすると x ≠ y (∵2つ目の矢印は特別な赤矢印)
  • γ の d+1 文字目は x、β の d+1 文字目は y であり、γ が β のprefixであることに矛盾する ■

特別な赤矢印を辿る回数が k 回になるような最短の文字列の長さを  L_k とすると、

  •  L_k \gt L_{k-1}+L_{k-2}

(上の状況で α→β は特別な赤矢印とは限らないが、βの前に辿った最後の特別な赤矢印の直前の文字列の長さは |α| 以上)
L を帰納的に求めるとfibonacci数的になっているため、特別な赤矢印を辿る回数は O(log N) 回であることが示せる。ちなみに log の底は黄金比 φ =  \frac {1+{\sqrt {5}}}{2}で、最悪ケースは fibonacci word

実装等はこの記事を参考にするといいでしょう。ここも良さそう。

応用問題

xmas contest 2015 D - Destroy the Duplicated Poem
問題概要を一口で説明すると「Trie木が与えられるので各頂点に対して赤矢印を求めよ」です。
普通にMPをやろうとすると、aaa...aaときてそのあとにbやらcやらと枝分かれしまくるケースとかで計算量が2乗に爆発してしまいます。
そこで、KMPを使えば遷移が常にO(log N)で抑えられてしまいます。やったー。
ソースコード
木上でやるとなると少し実装がトリッキーになるので頑張って混乱しないように整理して実装しましょう。
ちなみに想定解は違う解法だったので、期せずしてKMPの良い例題を作ってしまったらしい。