algorithm_rs/
string.rs

1#[allow(clippy::needless_range_loop)]
2pub fn z(s: &str) -> Vec<usize> {
3    let len = s.len();
4    let s: Vec<char> = s.chars().collect();
5
6    let mut ans = vec![0; len];
7    ans[0] = len;
8
9    let mut i = 1;
10    let mut j = 0;
11
12    while i < len {
13        while i + j < len && s[j] == s[i + j] {
14            j += 1
15        }
16        ans[i] = j;
17
18        if j == 0 {
19            i += 1;
20            continue;
21        }
22
23        let mut k = 1;
24        while i + k < len && k + ans[k] < j {
25            ans[i + k] = ans[k];
26            k += 1
27        }
28
29        i += k;
30        j -= k;
31    }
32
33    ans
34}
35
36#[cfg(test)]
37mod test_z_algorithm {
38    use crate::string::z;
39
40    #[test]
41    fn it_works() {
42        assert_eq!(z("ISSISSIPPIM"), vec![11, 0, 0, 4, 0, 0, 1, 0, 0, 1, 0]);
43    }
44}
algorithm_rs/string.rs

algorithm_rs/
string.rs
