Struct Matcher

pub struct Matcher<'a, C: Eq> {
    pub pattern: &'a [C],
    pub fail: Vec<usize>,
}

Single-pattern matching with the Knuth-Morris-Pratt algorithm

Fields

pattern: &'a [C]

The string pattern to search for.

fail: Vec<usize>

KMP match failure automaton. fail[i] is the length of the longest proper prefix-suffix of pattern[0..=i].

Implementations

impl<'a, C: Eq> Matcher<'a, C>

pub fn new(pattern: &'a [C]) -> Self

Precomputes the automaton that allows linear-time string matching.

Example

use contest_algorithms::string_proc::Matcher;
let byte_string: &[u8] = b"hello";
let utf8_string: &str = "hello";
let vec_char: Vec<char> = utf8_string.chars().collect();

let match_from_byte_literal = Matcher::new(byte_string);
let match_from_utf8 = Matcher::new(utf8_string.as_bytes());
let match_from_chars = Matcher::new(&vec_char);

let vec_int = vec![4, -3, 1];
let match_from_ints = Matcher::new(&vec_int);

Panics

Panics if pattern is empty.

pub fn kmp_match(&self, text: impl IntoIterator<Item = C>) -> Vec<usize>

KMP algorithm, sets @return[i] = length of longest prefix of pattern matching a suffix of text[0..=i].