最高に使いやすい Manacher のアルゴリズムの実装方法

参考文献：文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

普通の Manacher のアルゴリズム

入力 $s$ の長さが $n$ のとき、普通の Mancher のアルゴリズムは、$A_i$ が $s$ の場所 $s_i$ を中心とした「回文半径」であるような長さ $n$ の数列を返します。$s_i$ を中心とした回文半径が $A_i$ であるというのは、$s_i$ を中心とした回文の長さの最大値が $2 A _ i - 1$ であることです。したがって回文半径 $A_i$ は常に $1$ 以上です。

回文半径のよくある使い方

回文半径があると任意の奇数長の部分文字列が回文かどうかがわかったりして嬉しいのですが、でもやっぱり偶数長のものもほしいですよね。というわけで、すぬけさんはこう仰っております：

ちなみに、普通のManacherをやると奇数長の回文しか検出できませんが、「a$b$a$a$b」みたいにダミー文字を間に挟むと偶数長のものも検出できるようにできます。

また、Library Checker さん もこれを前提とした出力形式になっています。

長さ $2n - 1$ より長さ $2n + 1$ のほうが使いやすくありませんか？

先頭と末尾にもダミー文字を入れて $a$b$a$a$b$ のようにすると長さが $2$ 増えます。こうしておくと、$s([l, r[)$ が回文であるような $0 \le l \le r \le n$ に関する $l + r$ の最大値が $a_i$ になります。好みの範疇ですれども、こうすると添字がわかりやすかったり、なにより $n = 0$ でバグらないのが嬉しいところだと思います。

例えば $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]$ です。

最高に使いやすい Manacher のアルゴリズムの実装方法

すぬけさんの実装とほとんど同じですが、すぬけさんは $s \left ( \left [ i - j , i + j \right [ \right )$ （閉区間）が回文であることを保っていたところ、私の実装では $s \left ( \left [ \frac { i - j } { 2 } , \frac { i + j } { 2 } \right [ \right )$（開区間）が回文です。つまり $i$ が回文の中心の $2$ 倍、$j$ が回文の長さです。

他細かい注意点です。

• $i$ と $j$ の偶奇が常に揃っている状態を保ちます
• ［j += 2 のところ］回文半径が $1$ 文字増えると回文は $2$ 長くなります
• ［if j == 0 のところ］continue のところを消すと j -= k でオーバーフローします。回文半径は $1$ 以上である一方、回文長さは $0$ になることがあるからです。（相異なる文字の隙間のときや、先頭のとき、末尾のとき）

あとは大体同じです。$i, j$ の代わりに $l = (i - j) / 2, r = (i + j) / 2$ を管理するのもありな気もしたり、実装バリエーションはまだありそうですから、考案したらぜひとも共有していただけると嬉しいです！

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 {
        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;
        }
        let mut k = 1;
        while k <= i && k + a[i - k] < j {
            a[i + k] = a[i - k];
            k += 1;
        }
        i += k;
        j -= k;
    }
    a
}