Z アルゴリズム

概要

与えられた文字列 \(S\) について, \[Z_i = \mathrm{len}(\mathrm{longest\_common\_prefix}(S, S[i:]))\] なる配列 \(Z\) を線形時間で求めるアルゴリズム. ここで \(S[i:]\) とは \(i\) 文字目以降を切り出した部分文字列で, \(Z_i\) とは \(S\)\(S[i:]\) との最長共通接頭辞の長さのこと. 特に \(i=0\) のときは \(S[0:]=S\)\(Z_0 = \mathrm{len}(S)\).

              a  b  c  a  a  b  c
Z(abcaabc) = [7, 0, 0, 1, 3, 0, 0]

Z アルゴリズムによる文字列検索

文字列 \(S\) 中に \(T\) が部分文字列として出現するかの検索が Z アルゴリズムによって行える. すなわち, \(T\)\(S\) 及び特別な文字 @ (仮にこれは \(S\) にも \(T\) にも出現しない文字だとする)を結合した \(T@S\) という文字列を Z アルゴリズムに渡して配列 \(Z\) を構成し, その \(S\) に当たる後半に \(\mathrm{len}(T)\) が登場する場所を見ればよい.

fn z(s: &str) -> Vec<usize> {
    let s: Vec<char> = s.chars().collect();
    let n = s.len();
    let mut z = vec![0; n];
    z[0] = n;
    let mut i = 1;
    let mut j = 0;
    while i < n {
        while i + j < n && s[j] == s[i + j] { j += 1 }
        if j == 0 { i += 1; continue }
        z[i] = j;
        let mut k = 1;
        while i + k < n && k + z[k] < j {
            z[i + k] = z[k];
            k += 1;
        }
        i += k;
        j -= k;
    }
    z
}

fn z_search(s: &str, pattern: &str) -> Option<usize> {
    let m = pattern.len();
    let t = pattern.to_string() + ";$" + s;
    let table = z(&t);
    for i in 0..s.len() {
        if table[i + m + 2] == m { return Some(i) }
    }
    None
}