概要

Mancher のアルゴリズムは与えられた長さ $n$ の文字列 $s$ に対して、各文字の回文半径（その文字を中心とした回文の長さ引く $1$ 割る $2$）を計算するアルゴリズムです。これの出力要件とアルゴリズムを少し変えることで、実装の複雑さはほとんど変わらず、より使いやすいものにすることができます。

方針

各 $i$（$0 \le i \le 2n$）に対して、$l + r = i$ を満たす最大の回文区間 $[l, r[ \subseteq [0, n[$ の長さ $r - l$ を $A _ i$ と定め、これを計算することにしましょう。こうすると偶数長回文に対応しやすいです。（なおこれは $s$ の先頭と間と末尾にダミー文字を入れたものの、もとの定義での回文配列に一致します。）

例えば $s = \text{“mississippi”}$ のとき、$A = [0, 1, 0, 1, 0, 1, 4, 1, 0, 7, 0, 1, 4, 1, 0, 1, 0, 1, 4, 1, 0, 1, 0]$ となります。

アルゴリズム

従来のアルゴリズム同様、まずは回文区間 $[0, 1[$ から始めて、

1. 伸ばせるだけ伸ばす
2. 境界に達しない限り、回文配列を書き写す
3. 境界に達したら現在の回文区間を覚えて 1 に戻る

というふうにすればよいです。

実装は次のようになります。回文区間 $[l, r[$ に対応して $i = l + r, j = r - l$ を管理しています。なお 1 の結果 $j = 0$（空区間）になった場合は例外的な対応が必要なことに注意です。これは従来のアルゴリズムでは必要なかったステップです。

pub fn manacher<T: Eq>(s: &[T]) -> Vec<usize> {
    let n = s.len();
    let mut a = vec![0; 2 * n + 1];
    let mut i = 1;
    let mut j = 1;
    while i <= 2 * n {
        // 1. 伸ばせるだけ伸ばす
        while j < i && i + j < 2 * n && s[(i - j) / 2 - 1] == s[(i + j) / 2] {
            j += 2;
        }
        a[i] = j;
        // ※ 空区間になった場合は例外的な対応が必要
        if j == 0 {
            i += 1;
            j = 1;
            continue;
        }
        // 2. 境界に達しない限り、回文配列を書き写す
        let mut k = 1;
        while k <= i && k + a[i - k] < j {
            a[i + k] = a[i - k];
            k += 1;
        }
        // 3. 境界に達したら現在の回文区間を覚えて 1 に戻る
        i += k;
        j -= k;
    }
    a
}

参考文献

• Manacher, Glenn. "A New Linear-Time``On-Line''Algorithm for Finding the Smallest Initial Palindrome of a String." Journal of the ACM (JACM) 22.3 (1975): 346-351.
• Longest palindromic substring - Wikipedia
• 文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
• 最長回文 (Manacher’s algorithm) - yaketake08's 実装メモ