Manacher (string/manacher/src/lib.rs)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-01-01 00:11:18+09:00

Description

Reference

• https://snuke.hatenablog.com/entry/2014/12/02/235837

Verified with

• verification/library-checker/enumerate_palindromes/src/main.rs

Code

pub fn manacher<T: Copy + PartialEq>(s: &[T]) -> Vec<usize> {
    if s.len() == 0 {
        return vec![];
    }
    let mut res = vec![0; s.len()];
    let mut i = 0;
    let mut j = 0;
    while i < s.len() {
        while i >= j && i + j < s.len() && s[i - j] == s[i + j] {
            j += 1;
        }
        res[i] = j;
        let mut k = 1;
        while i >= k && i + k < s.len() && k + res[i - k] < j {
            res[i + k] = res[i - k];
            k += 1;
        }
        i += k;
        j -= k;
    }
    res
}

Back to top page