competitive/string/
knuth_morris_pratt.rs

1#[derive(Clone, Debug)]
2pub struct KnuthMorrisPratt<T: Eq> {
3    pattern: Vec<T>,
4    table: Vec<usize>,
5}
6impl<T: Eq> KnuthMorrisPratt<T> {
7    pub fn new(pattern: Vec<T>) -> Self {
8        let mut table = vec![0; pattern.len() + 1];
9        for i in 1..pattern.len() {
10            let mut j = table[i - 1];
11            while j > 0 && pattern[i] != pattern[j] {
12                j = table[j - 1];
13            }
14            table[i] = j + (pattern[i] == pattern[j]) as usize;
15        }
16        Self { pattern, table }
17    }
18    pub fn search_all(&self, s: &[T]) -> Vec<usize> {
19        let mut res = vec![];
20        let mut j = 0;
21        for (i, s) in s.iter().enumerate() {
22            while j > 0 && s != &self.pattern[j] {
23                j = self.table[j - 1];
24            }
25            if s == &self.pattern[j] {
26                j += 1;
27            }
28            if j == self.pattern.len() {
29                res.push(i - (j - 1));
30                j = self.table[j - 1];
31            }
32        }
33        res
34    }
35}