competitive_programming_lib/Algorithms/
kmp.rs

1pub fn kmp_pattern_search(text: &str, pattern: &str) -> Vec<usize> {
2    let mut lps = vec![0; pattern.len()];
3    let mut lps = vec![0; pattern.len()];
4    let mut j = 0;
5    compute_lps(pattern, &mut lps);
6
7    let mut matches = Vec::new();
8    let text_bytes = text.as_bytes();
9    let pattern_bytes = pattern.as_bytes();
10    let mut i = 0;
11
12    while i < text.len() {
13        if pattern_bytes[j] == text_bytes[i] {
14            i += 1;
15            j += 1;
16        }
17
18        if j == pattern.len() {
19            matches.push(i - j);
20            j = lps[j - 1];
21        } else if i < text.len() && pattern_bytes[j] != text_bytes[i] {
22            if j != 0 {
23                j = lps[j - 1];
24            } else {
25                i += 1;
26            }
27        }
28    }
29
30    matches
31}
32
33fn compute_lps(pattern: &str, lps: &mut [usize]) {
34    let mut length = 0;
35    let mut i = 1;
36
37    while i < pattern.len() {
38        if pattern.as_bytes()[i] == pattern.as_bytes()[length] {
39            length += 1;
40            lps[i] = length;
41            i += 1;
42        } else {
43            if length != 0 {
44                length = lps[length - 1];
45            } else {
46                lps[i] = 0;
47                i += 1;
48            }
49        }
50    }
51}