po

Z-Algorithm

名前がかっこいい。

Z-Algorithm

z[i]:=|LCP(s, s[i, |s|))| (sとs[i, |s|)の最長共通接頭辞の長さ)

をO(|s|)で求めるもの。

z[]の構築

愚直にやるとO(n2)になる。z[i]を求めるのにz[j] (j<i)の情報をうまく使ってやるとO(n)で求まる。

z[0]=|s| は明らか

i=1, len=0として、lenを1ずつ増やしていき愚直に1文字ずつ比較していった結果、z[i]=lenと求まったとする。このときs[0, len)=s[i, i+len)となっているので、これを利用してz[i+1], z[i+2], ..., z[i+len-1]を求めることを考える。

k=1から始めてk+z[k]<lenを満たす間kを1ずつ増やしていく。不等式の条件はs[k, k+z[k])がs[0, len)に含まれることを意味している。s[0, len)=s[i, i+len)だったので上の不等式を満たすとき、s[k, k+z[k])=s[i+k, i+(k+z[k]))も成り立つ。つまり、z[i+k]=z[k]と求まる。

k+z[k]<lenが崩れたとき、つまり[k, k+z[k])の右側が[0, len)からはみ出たとき、はみ出した部分でどうなっているか分からないので上のようにzを更新することはできない。ただ、z[k]≧len-kなのでs[k, len)=s[0, len-k)が成り立ち、s[k, len)=s[i+k, i+len)とあわせて、s[i+k]からlen-k文字はsのprefixと一致していることが分かる。つまり、i+=k, len-=kと更新して、愚直にlenを伸ばしていくパートに戻る。

図を見たほうが早いかも。(訂正:右側の青色の長さはi+lenではなくてlenでした)

https://cdn-ak2.f.st-hatena.com/images/fotolife/p/poyopoyoyon/20171125/20171125214318_original.png

https://cdn-ak2.f.st-hatena.com/images/fotolife/p/poyopoyoyon/20171125/20171125212341_original.png

参考

http://snuke.hatenablog.com/entry/2014/12/03/214243

実装がシンプルですごい。これがないと分からなかった。