competitive/string/
z_algorithm.rs

1#[derive(Clone, Debug)]
2pub struct Zarray {
3    z: Vec<usize>,
4}
5impl Zarray {
6    pub fn new<T: Eq>(s: &[T]) -> Self {
7        let n = s.len();
8        let mut z = vec![0; n];
9        z[0] = n;
10        let (mut i, mut j) = (1, 0);
11        while i < n {
12            while i + j < n && s[j] == s[i + j] {
13                j += 1;
14            }
15            z[i] = j;
16            if j == 0 {
17                i += 1;
18                continue;
19            }
20            let mut k = 1;
21            while i + k < n && k + z[k] < j {
22                z[i + k] = z[k];
23                k += 1;
24            }
25            i += k;
26            j -= k;
27        }
28        Self { z }
29    }
30    pub fn search<T: Eq>(s: &[T], pat: &[T], sep: T) -> Vec<usize> {
31        let mut res = vec![];
32        let mut t = vec![];
33        t.extend(pat);
34        t.push(&sep);
35        t.extend(s);
36        let zarray = Self::new(&t);
37        for i in 0..t.len() {
38            if zarray[i] == pat.len() {
39                res.push(i - pat.len() - 1);
40            }
41        }
42        res
43    }
44}
45impl std::ops::Index<usize> for Zarray {
46    type Output = usize;
47    fn index(&self, index: usize) -> &usize {
48        &self.z[index]
49    }
50}
competitive/string/z_algorithm.rs

competitive/string/
z_algorithm.rs
