Manacher による最大長回文探索アルゴリズム

参考

• Spaghetti Source - 最長回文 (Manacher)

概要

文字列 \(s\) が与えられた時、\(s\) の各点を中心とする回文の最大長を求める. ここで \(n = |s|\) とすると、各点とは

• \(i = 1,2, \ldots, n\) 及び
• \(j = (1, 2), (2, 3), \ldots, (n-1, n)\)

の二種類のこと. \(i\) は各文字に対応し、\(j\) は隣り合った2文字の間を指す. これを中心とする (連続) 部分文字列とは

• 中心 \(i\) に就いて \(s(i - x, i + x)\) または
• 中心 \(j = (j_0, j_1)\) に就いて \(s(j_0 - x, j_1 + x)\)

のこと.

入出力

返り値は \[1, (1, 2), 2, (2, 3), 3, \ldots, n-1, (n-1, n)\] を中心としたする回文の最大長を収めたベクトル.

/// String - Test Palindric - Manacher Algorithm
pub fn manacher<A: Ord>(s: &Vec<A>) -> Vec<usize> {
    let n = s.len();
    let mut r = vec![0; 2 * n - 1];
    let mut i = 0;
    let mut j = 0;
    while i < 2 * n - 1 {
        while i >= j && i + j + 1 < 2 * n && s[(i - j) / 2] == s[(i + j + 1) / 2] {
            j += 1;
        }
        r[i] = j;
        let mut k = 1;
        while i + k < 2 * n - 1 && i >= k && r[i] >= k && r[i - k] != r[i] - k {
            r[i + k] = std::cmp::min(r[i - k], r[i] - k);
            k += 1;
        }
        i += k;
        j = if j > k { j - k } else { 0 }
    }
    r
}

#[cfg(test)]
mod test_manacher {
    use crate::string::manacher::*;

    #[test]
    fn it_works() {
        assert_eq!(manacher(&"a".chars().collect()), vec![1]);
        assert_eq!(manacher(&"ab".chars().collect()), vec![1, 0, 1]);
        assert_eq!(manacher(&"aba".chars().collect()), vec![1, 0, 3, 0, 1]);
        assert_eq!(manacher(&"abc".chars().collect()), vec![1, 0, 1, 0, 1]);
    }
}