マナカーのアルゴリズム（Manacher's Algorithm）で最長回文部分文字列をO(n)で求める方法

文字列の中から最も長い回文部分文字列を効率よく見つけたい場合、マナカーのアルゴリズム（Manacher's Algorithm）が非常に有効です。この手法では、文字列内の各文字を中心として、左右のポインタを用いて回文が成立するかどうかを順に確認していきます。あわせて、回文に関する情報を記録するための補助配列を用意しておくことで、各位置における回文の長さを容易に参照できるようになります。すべての文字に対してこの処理を実行し、文字列全体の走査が完了した時点で、構築した配列から最長の回文部分文字列を特定できます。

このアルゴリズムの計算量は O(n) です。全文字を中心として毎回両方向へ展開する単純な全探索（O(n²)）と比較して、大幅に高速化できる点が最大の特徴といえます。

入力と出力

入力：
文字列： "levelup"
出力：
最長の回文： level

アルゴリズムの手順

longestPalindrome(text)

入力 − 最長の回文を検索する対象テキスト

出力 − テキスト中に含まれる最長の回文

Begin
    n := text size
    if n = 0, then
        return null string
    n := 2n+1

    define array longPal of size n
    longPal[0] := 0 and longPal[1] := 1
    centerIndex := 1
    rightIndex := 2
    right := 0
    maxPalLength := 0
    maxCenterIndex := 0
    start := -1 and end := -1, diff := -1

    for right := 2 to n-1, do
        left := 2*centerIndex – right
        longPal[right] := 0
        diff := rightIndex – right
        if diff > 0, then
            longPal[right] := minimum(longPal[left], diff)
            while (right + longPal[right]) < n AND (right - longPal[right]) > 0 AND
                (right + longPal[right]+1)mod 2 = 0 OR
                text[(right + longPal[right] + 1)/2] = text[(right - longPal[right]-1)/2], do
                increase longPal[right] by 1
        done

        if longPal[right] > maxPalLength, then
            maxPalLength := longPal[right]
            maxCenterIndex := right
        if (right + longPal[right]) > rightIndex, then
            centerIndex := right
            rightIndex := right + longPal[right]
    done
    start := (maxCenterIndex – maxPalLength)/2
    end := start + maxPalLength – 1

    palindrome = substring of text[start..end]
    return palindrome
End

C++による実装例

#include<iostream>
using namespace std;

int min(int a, int b) {
    return (a<b)?a:b;
}

string longestPalindrome(string mainString) {
    int n = mainString.size();
    if(n == 0)
        return "";
    n = 2*n + 1; // 次の位置をカウント
    int longPal[n]; // 最長回文の長さを格納する配列
    longPal[0] = 0; longPal[1] = 1;
    int centerIndex = 1;
    int rightIndex = 2;
    int right = 0, left;
    int maxPalLength = 0, maxCenterIndex = 0;
    int start = -1, end = -1, diff = -1;

    for (right = 2; right < n; right++) {
        left  = 2*centerIndex-right; // 中心と右位置から左位置を計算
        longPal[right] = 0;
        diff = rightIndex - right;

        if(diff > 0)
            longPal[right] = min(longPal[left], diff);
        while ( ((right + longPal[right]) < n && (right - longPal[right]) > 0) &&
            ( ((right + longPal[right] + 1) % 2 == 0) ||
            (mainString[(right + longPal[right] + 1)/2] == mainString[(right - longPal[right] - 1)/2] ))) {
            longPal[right]++;
        }

        if(longPal[right] > maxPalLength) {     // 最大回文長を更新
            maxPalLength = longPal[right];
            maxCenterIndex = right;
        }

        if (right + longPal[right] > rightIndex) {
            centerIndex = right;
            rightIndex = right + longPal[right];
        }
    }

    start = (maxCenterIndex - maxPalLength)/2;
    end = start + maxPalLength - 1;
    string palindrome;

    for(int i=start; i<=end; i++)
        palindrome += mainString[i];
    return palindrome;
}

int main(int argc, char *argv[]) {
    string mainString, palindrome;
    cout << "Enter String:";
    cin >> mainString;
    palindrome = longestPalindrome(mainString);
    cout << "Longest palindrome is: " << palindrome << endl;
}

出力結果

Enter String: levelup
Longest palindrome is: level