competitive_programming_lib/Algorithms/
kmp.rs1pub 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}