cp_library_rs/string/
z.rs

1//! Z-Algorithm
2
3/// 文字列 s に対して，
4///
5/// ```text
6/// z[i] := lcp(s, s[i..])
7/// ```
8///
9/// を満たす配列 z を求める．
10///
11/// - 時間計算量: $`O(|s|)`$
12///
13/// ---
14///
15/// 参考:
16/// - <https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05>
17pub fn z_algorithm<T: PartialEq>(s: &[T]) -> Vec<usize> {
18    let n = s.len();
19    if n == 0 {
20        return vec![];
21    }
22
23    let mut z = vec![0; n];
24    z[0] = n;
25
26    let mut i = 1;
27    let mut j = 0;
28
29    while i < n {
30        while i + j < n && s[j] == s[i + j] {
31            j += 1;
32        }
33        z[i] = j;
34
35        if j == 0 {
36            i += 1;
37            continue;
38        }
39
40        let mut k = 1;
41        while k < j && k + z[k] < j {
42            z[i + k] = z[k];
43            k += 1;
44        }
45        i += k;
46        j -= k;
47    }
48
49    z
50}
cp_library_rs/string/z.rs

cp_library_rs/string/
z.rs
