Z algorithmの文章による説明

Z algorithmを図に頼らずに理解したかったので書きました．

長さの文字列にZ algorithmを適用することを考えます．

以下の説明では文字列中の各文字を0-basedで指定します¹．の文字目をと表記します．また，の文字目から文字目までを取り出した部分文字列をと表記します．のときは空文字列とし，空文字列同士は一致するとします．便宜上を任意の文字に一致しない文字と取り決めます．

に対し，をかつを満たす以下の非負整数とします．つまり，はとの最長共通接頭辞の長さを表します．なのでです．

以下，とし，あるについてが既知であるとします．また，とします．の定義より，かつです．

について，この順に]を求めることを考えます．よりを求めるときにはは既知であり，この値を利用します．各について，の値により以下のように場合分けして考えます．

• のとき

  より，なので以下の2つの関係が成り立ちます．

  • 
  • 

  の文字目以降の文字との文字目以降の文字とが，の接頭辞と文字目で不一致となることも含めて一致しているのでであると分かります²．

• のとき

  及びより，が成り立ち，であると分かります．を確定するためにとを比較する必要がありますが，最初の文字については既に一致していることが判明しているため，比較処理を省略することができます．

Z algorithmではとなるが見つかった時点でをで置き換え， 最初の文字の比較処理を省略してを求めることでが既知である最初の状態に戻します．このようにすることで文字を比較する位置が後退せず，全体の計算量がになります．

実装例 (Rust)

pub fn z_algorithm<T>(seq: &[T]) -> Vec<usize>
where
    T: Eq,
{
    if seq.is_empty() {
        return vec![];
    }

    let n = seq.len();

    let mut lengths = vec![0; n];
    lengths[0] = n;

    let mut cursor = 1;
    let mut common_len = 0;
    while cursor < n {
        while cursor + common_len < n && seq[cursor + common_len] == seq[common_len] {
            common_len += 1;
        }

        if common_len == 0 {
            cursor += 1;
            continue;
        }

        lengths[cursor] = common_len;

        let mut shift = 1;
        while shift + lengths[shift] < common_len {
            lengths[cursor + shift] = lengths[shift];
            shift += 1;
        }

        cursor += shift;
        common_len -= shift;
    }

    lengths
}

---

1. の先頭の文字は文字目，最後の文字は文字目となります．↩
2. 人の課題を写したら全く同じ間違え方をしていてバレたという話と少し似ています．↩