(メモ Z-Algorithm)
参考
いちから実装するときは、次のような図を書いて考えるとよさそう
https://gyazo.com/89721462c453efeec7a73968849a15ca
愚直な方法で $ Z_i の値を計算できたとする
$ Z_{i + j}を知りたい
$ Z_{i+j} \ge Z_jが成り立つ
特に$ j + Z_j < lならば 等号成立
$ j + Z_j \ge lのときは
"共通接頭辞の長さ" を$ l - j
"開始位置" を$ i \to i + jにずらす
とする必要がある
いい感じの具体例を手軽に作りにくい気がする
一応↓の記述も残しておく
文字列 S があったとき、S と「S の i 文字目から始まる文字列 (i = 0, 1, 2, ...)」との最長共通接頭辞の長さ Zi を求める
たとえば Z[0] = S.size
赤や青になっているところは同じ文字列 (長さも等しい)
図のように
S の先頭から j 文字切り出した文字列
S の i 文字目から j 文字 ... 文字列
が一致している状況 (★) を考える
https://gyazo.com/cac10b53654ca3cff6d3779e6a8c9009
とりあえず Zi ≧ j は確定する
青部分のすぐ右の文字 (S[j + 1] と S[i + j + 1]) が一致していたら、さらに青を伸ばせる
いつかは不一致になるから初めてそうなった場所を j1 とする
このとき Zi = j1 となる (j1 は 0-indexed であることに注意)
上の図で青部分は文字列として等しいから
それらから同じ区間を切り出しても等しい文字列になっている (*)
よって Z_(i+k) を求めるには S の i+k 文字目から始まる文字列のかわりに
S の k 文字目から始まる文字列を考えてもよい (だいたい)
しかし、Zk は計算済みだからすぐに Z_(i+k) = Zk と求まる
https://gyazo.com/9ca32ab537b21b108f3b1e01fedd7d52
だいたい ok と言ったのは k + Zk ≧ j1 となる状況を考慮していないからである
(*) が使えるのは青の"内部"から文字列を切り出したときのみで、
上の状況では S の k + Zk 文字目が青の右側に飛び出しているから適合しない
k + Zk ≧ j1 となる最初の k を k1 とする
Z_(i+k1) 以降を求めるには j = 0 として一番はじめの状況 (★) に戻らなければいけない
かと思いきや、そうでもない
それぞれの青の中で赤になっている部分は
S の接頭辞になっている (赤部分の長さは Z_(k1) 以下のため) から
その長さの分は計算を省略できる。Z_(i+k1) ≧ 赤の長さ ということ
気をつけながら見ると赤の長さは j1-k1 になっている
一応 (★) で満たしていた条件を i+k1, j1-k1 について確認すると
S の長さ j1-k1 の接頭辞
S の i+k1 文字目から j1-k1 文字切り出した文字列
となり、確かにこれらは等しい
よって (★) に戻って同様にやればよい