競プロ用ライブラリを作る Advent Calendar 2024の19日目です.
Z Algorithmって?
何らかの配列sが与えられたときに, こういう配列を作ります
-
z[i]は「sとs[i..]の先頭のいくつの要素が一致しているか」を表す
愚直に書くなら以下のようになります
fn naive_z(slice: &[u8]) -> Vec<usize> {
let mut z = vec![];
// slice自身とslice[0..]は完全に一致するので, 長さを入れておく
z.push(slice.len());
for i in 1..slice.len() {
// 先頭を比較する配列
let sub = &slice[i..];
let mut j = 0;
loop {
// 違う箇所を見つける or 文字列の最後まで見たら, その場所を結果の配列に入れる
if slice.get(j) != sub.get(j) {
z.push(j);
break;
}
// そういう箇所が見つかるまで調べ続ける
j += 1;
}
}
z
}
この愚直は最悪$O\left(N^2\right)$になりますが, このアルゴリズムを使えば$O(N)$でできます.
仕組み
愚直な方法で時間がかかるときはatatatata...みたいな大規模に先頭が一致して調べるのに時間がかかるケースです.
例としてatatata_and_atatataという列を計算したときの結果を見てみます
a t a t a t a _ a n d _ a t a t a t a
---------------------------------------------------------
19 0 5 0 3 0 1 0 1 0 0 0 7 0 5 0 3 0 1
^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^
^^^の範囲が一致していますね. 13文字目に「7文字一致している」という情報があるから, そこから6文字は先頭の情報が使いまわせてしまうわけです.
注意すべきが, tentekotentenみたいなケースで,
t e n t e k o t e n t e n
---------------------------------------
13 0 0 2 0 0 0 5 0 0 3 0 0
^^^^^^^^^^ ^^^^^^^^^^
この通り, 一致しません. 11文字目の「先頭3文字」は一致している範囲からはみ出しているのでそのままでは使いまわせず, どれだけはみ出すか調べる必要があります.
原理はこういう感じなので, これを実装するだけです. が, かなりややこしいので注意して実装しましょう.
pub fn z(slice: &[u8]) -> Vec<usize> {
let n = slice.len();
// 結果を入れる配列
let mut z = Vec::with_capacity(n);
// 先頭の要素は全部一致してるので, 配列の長さを入れる
z.push(n);
// 利用する「一致している範囲」の左端と右端
// 最初は仮に両方1を入れていて, 区間の大きさが0なので「最初」
let mut l = 1;
let mut r = 1;
// ループの各回で1つずつzに要素を追加していく
for i in 1..n {
// 完全に一致している範囲に収まっていたら, そのまま追加して終了
if l < i && z[i - l] + i < r {
z.push(z[i - l]);
continue;
}
// この後を実行するのは
// - はみ出した
// - 一致している範囲を使い切ってまだ情報が無いところに突入した
// のどちらかです
// どちらにしても, 今計算したい地点から新たな「一致している範囲」を作り直します
// rはここで不一致(一致している区間の終わり)を探す用の変数になります
// - はみ出した場合は, 一致している区間の中では完全に一致していた, ということなので,
// 探索はr以降を見ればいいです
// - 範囲を使い切った場合は情報がないのではじめ(つまりi)から調べればよいです
// このケースではこの時点でr <= iになってるので, r < iのときにr = iに設定してやります
if r < i {
r = i;
}
// 前述の通り, 新しい一致している区間の左端はiです
l = i;
// 一致していない場所を探します
while slice.get(r) == slice.get(r - i) {
r += 1;
}
z.push(r - l);
}
z
}
実装
上のサンプルコードと殆ど何も変わりません.
まとめ
いかがでしたか?
明日は引き続き天才線形時間アルゴリズムを実装します.