Manacher

For an array \(A\) of length \(n\), manacher(A) returns a vector \(M\) where, for every \(i \in \left[0, n\right)\), \(A_{i-j} = A_{i+j}\) holds for every \(j \in \left[0, M_i \right)\).

Additional modification should be added by a user to use this function for finding every palindromes among subsequences of a string.

Example

fn main() {
let s = "abracadacabra".as_bytes();
let man = manacher(s);
println!("{:?}", man); // [1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 1]

for i in 0..s.len() {
    println!(
        "{}",
        std::str::from_utf8(&s[i + 1 - man[i]..i + man[i]]).unwrap()
    );
}
}

fn manacher<T: Eq>(arr: &[T]) -> Vec<usize> {
    let n = arr.len();
    let mut mana: Vec<usize> = vec![1; n];
    let mut r: usize = 1;
    let mut p: usize = 0;

    for i in 1..arr.len() {
        if i + 1 >= r {
            mana[i] = 1;
        } else {
            let j = 2 * p - i;
            mana[i] = mana[j].min(r - i);
        }

        while mana[i] <= i && i + mana[i] < n {
            if arr[(i - mana[i])] != arr[(i + mana[i])] {
                break;
            }
            mana[i] += 1;
        }

        if r < mana[i] + i {
            r = mana[i] + i;
            p = i;
        }
    }

    mana
}

Code

fn manacher<T: Eq>(arr: &[T]) -> Vec<usize> {
    let n = arr.len();
    let mut mana: Vec<usize> = vec![1; n];
    let mut r: usize = 1;
    let mut p: usize = 0;

    for i in 1..arr.len() {
        if i + 1 >= r {
            mana[i] = 1;
        } else {
            let j = 2 * p - i;
            mana[i] = mana[j].min(r - i);
        }

        while mana[i] <= i && i + mana[i] < n {
            if arr[(i - mana[i])] != arr[(i + mana[i])] {
                break;
            }
            mana[i] += 1;
        }

        if r < mana[i] + i {
            r = mana[i] + i;
            p = i;
        }
    }

    mana
}