Struct Manacher 

pub struct Manacher {
    pub start: usize,
    pub length: usize,
    pub radii: Vec<usize>,
}

Result of running manacher on a byte string.

The radius array radii is indexed by transformed position. Position i of the transformed string corresponds either to a real character (when i is odd in the # c # c # … layout) or to a gap between characters (when i is even). radii[i] is the palindromic radius in transformed coordinates; the length of the palindrome centred there, measured in original characters, is exactly radii[i].

Fields

start: usize

Start index (inclusive) of a longest palindromic substring in the input.

length: usize

Length in bytes of a longest palindromic substring (0 for empty input).

radii: Vec<usize>

Per-center radius array in transformed coordinates. Its length is 2 * n + 1 where n = input.len(). radii[i] equals the number of original characters spanned on each side of center i, i.e. the length of the palindrome centred at i in original-character units.

Implementations

impl Manacher

pub fn longest<'a>(&self, input: &'a [u8]) -> &'a [u8]

Borrow the longest palindromic substring out of the original input.

Returns &input[start..start + length]. For an empty input this is the empty slice.

pub fn palindrome_count(&self) -> usize

Total number of palindromic substrings (each distinct occurrence counted once), derived from the radius array.

A palindrome centred at transformed position i with radius r (in original-character units) contains ⌈r / 2⌉ palindromic substrings that are themselves centred at i (itself, then peeling two characters at a time). Summing over all centers counts every palindromic substring of the original string exactly once, because each palindrome has a unique center in the transformed string.

Trait Implementations

impl Clone for Manacher

fn clone(&self) -> Manacher

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Manacher

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.