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] はどう計算すればいいでしょうか?
f:id:snuke:20170712160204p:plain
図の赤い矢印は i→A[i] を結んでいます。
A[9] を求めるステップは以下のとおりです。

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

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

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

KMP

下図のような青い矢印を考えます。
この青い矢印は「"次の文字"が異なるまで赤い矢印を辿った場所」に張られたものです。
f:id:snuke:20170712155859p:plain
実は先程の A[9] を求めるステップでは、青い矢印を赤い矢印の代わりに使っても正しい答えが求まります。
なぜなら、5→2 の矢印をたどるということは ? が b ではなかったということで、それなら 2 を試す必要はなくスキップしても同じで、同様に 1→0 の矢印もスキップして良いからです。

実はこれで1ステップの計算量をO(log N)で抑えることができます。
で、これがKMPのKです。
計算量を解析してみます。
「赤矢印を辿る」+「次の"次の文字"が異なる赤矢印までスキップする」というのを1ブロックとして考えます。
1ブロック進むごとに残りの長さが半分以下になっていくことを示せば、O(log N)になることが示せそうですね。

  • 「赤矢印を辿る」で半分以上進む場合:言うまでも半分以下になります。
  • 「赤矢印を辿る」で半分以上進まない場合:「次の〜スキップする」の方で半分以下まで減ることを示します。

f:id:snuke:20170717195852p:plain
図の緑と赤は文字を、青と紫は文字列を表します。
右端の赤矢印の長さを w とします。
図の文字列は周期が w であるため、次の赤矢印でもちょうど w 進みます。(w 進めることは明らかで、w 未満進むとすると前の赤矢印でもその分進めたはずなのでおかしい)
すると、進んだ先の"次の文字"も同じ文字(緑)なはずなのでスキップされるはずです。
で、次の赤矢印も w 進むはずで、スキップされて・・・というのが残りが w 未満になるまで続きます。
w が残りの長さの半分未満であったことを考えると、この場合でも1ブロック進むごとに残りの長さが半分以下になることが分かります。
以上、O(log N) の証明でした。

ちなみに Θ(log N) でもあることは "abacabadabacabae...." みたいな文字列を考えるとわかります。
文字種が2種類でも "0100010101000100" みたいな文字列(ace...が0でbd...が1)を考えると log N が作れます。
実装等はこの記事を参考にするといいでしょう。ここも良さそう。

応用問題

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