Module manacher 

Manacher’s algorithm for longest palindromic substring in linear time.

Reference: Glenn Manacher, “A New Linear-Time ‘On-Line’ Algorithm for Finding the Smallest Initial Palindrome of a String”, Journal of the ACM 22(3), 1975, pp. 346–351. The modern center/radius formulation used here is the standard textbook restatement.

Idea

A palindrome is either odd-length (centred on a character) or even-length (centred between two characters). To treat both uniformly, the input is transformed by interleaving a separator that occurs nowhere in the data:

"abba"  ->  ^#a#b#b#a#$

Every palindrome of the original string corresponds to an odd-length palindrome of the transformed string centred at one of the #/character slots, and vice versa. We compute, for each transformed position i, the radius p[i] = the largest r such that t[i-r..=i+r] is a palindrome.

The linear-time trick maintains the palindrome with the right-most boundary seen so far, (center, right). For a new position i inside that palindrome, the mirror position 2*center - i gives a free lower bound on p[i]; only the excess beyond the boundary is verified by explicit character comparisons, and each such comparison advances right, so the total work is O(n).

The sentinels ^ and $ (chosen here as two distinct synthetic markers that never compare equal to any data byte or to each other) remove the need for explicit bounds checks during expansion.

What is returned

manacher returns a Manacher bundling the longest palindromic substring together with its location and the full per-center radius array, from which every maximal palindrome — and the total count of palindromic substrings — can be recovered (Manacher::palindrome_count, Manacher::longest).

Input is treated as raw bytes (&[u8]); for ASCII this is the usual character-level notion of a palindrome.

Structs

Manacher

Result of running manacher on a byte string.

Functions

longest_palindrome_str

Convenience wrapper returning the longest palindromic substring of a &str as an owned String.

manacher

Compute the longest palindromic substring of input with Manacher’s algorithm in O(n) time.