Struct contest_algorithms::string_proc::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 utf8_string = "hello";

let match_from_byte_literal = Matcher::new(b"hello");

let match_from_bytes = Matcher::new(utf8_string.as_bytes());

let vec_char: Vec<char> = utf8_string.chars().collect();
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: &[C]) -> Vec<usize>

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