最長回文部分文字列の求め方｜動的計画法によるアルゴリズムとC++実装

文字列処理の古典的な問題のひとつに、「与えられた文字列の中から、回文となっている部分文字列のうち最も長いものを見つける」という最長回文部分文字列問題があります。

この問題を解くためには多くの部分問題を処理する必要があり、その中には互いに重複する（オーバーラップする）部分問題も含まれます。同じ計算を何度も繰り返すのは非効率なため、ここでは動的計画法（Dynamic Programming）が有効です。表（テーブル）にすでに求めた部分問題の結果を記録しておけば、それを再利用しながら後続の結果を効率的に導き出せるのです。

入力と出力

入力:
文字列。例: "thisispalapsiti"

出力:
最長の回文部分文字列と、その長さ。
最長回文部分文字列: ispalapsi
長さ: 9

アルゴリズム

ここで紹介する手法は、palTab[i][j] という真偽値テーブルを使います。「位置 i から j までの部分文字列が回文であれば true」という情報を格納するものです。

findLongPalSubstr(str)

入力 − 対象となる文字列。

出力 − 最長の回文部分文字列とその長さ。

Begin
    n := 与えられた文字列の長さ
    真偽値を格納する n x n のテーブル palTab を作成する
    palTab をすべて false で初期化する
    maxLen := 1

    for i := 0 to n-1, do
        palTab[i, i] := true        // 長さ1の文字列は必ず回文
    done

    start := 0
    for i := 0 to n-2, do
        if str[i] = str[i+1], then   // 隣接する2文字が一致すれば回文
            palTab[i, i+1] := true
            start := i
            maxLen := 2
        done
    done

    for k := 3 to n, do             // 長さ3以上の部分文字列を順に調べる
        for i := 0 to n-k, do
            j := i + k - 1
            if palTab[i+1, j-1] and str[i] = str[j], then
                palTab[i, j] := true
                if k > maxLen, then
                    start := i
                    maxLen := k
                done
            done
        done
    done
    文字列 str の start から maxLen 分の部分文字列を表示し、maxLen を返す
End

アルゴリズムのポイント

• 長さ1の部分文字列は常に回文であるため、まず対角成分 palTab[i][i] を true にします。
• 長さ2の部分文字列は、隣接する2文字が一致していれば回文です。
• 長さ3以上の場合は「両端の文字が等しく、かつ内側（i+1〜j-1）がすでに回文である」ことを確認します。これにより、小さい問題の結果を再利用できるのが動的計画法の利点です。

C++での実装例

#include<iostream>
using namespace std;

int findLongPalSubstr(string str) {
    int n = str.size();          // 入力文字列の長さを取得

    bool palCheckTab[n][n];      // i〜j の部分文字列が回文なら true

    for(int i = 0; i<n; i++)
        for(int j = 0; j<n; j++)
            palCheckTab[i][j] = false;   // すべて false で初期化

    int maxLength = 1;

    for (int i = 0; i < n; ++i)
        palCheckTab[i][i] = true;        // 長さ1の部分文字列は必ず回文

    int start = 0;
    for (int i = 0; i < n-1; ++i) {
        if (str[i] == str[i+1]) {        // 隣接する2文字が一致する場合
            palCheckTab[i][i+1] = true;
            start = i;
            maxLength = 2;
        }
    }

    for (int k = 3; k <= n; ++k) {       // 長さ3〜n の部分文字列を調べる
        for (int i = 0; i < n-k+1 ; ++i) {
            int j = i + k - 1;
            if (palCheckTab[i+1][j-1] && str[i] == str[j]) {  // 内側が回文で両端も一致
                palCheckTab[i][j] = true;
                if (k > maxLength) {
                    start = i;
                    maxLength = k;
                }
            }
        }
    }
    cout << "Longest palindrome substring is: " << str.substr(start, maxLength) << endl;
    return maxLength; // 長さを返す
}

int main() {
    char str[] = "thisispalapsiti";
    cout << "Length is: "<< findLongPalSubstr(str);
}

実行結果

Longest palindrome substring is: ispalapsi
Length is: 9

まとめ

このアルゴリズムは n×n のテーブルを使用するため、時間計算量・空間計算量ともに O(n²) となります。全ての開始・終了位置の組み合わせについて回文判定を表に記録しながら進むことで、無駄な再計算を避けられる点が大きな特徴です。より高速な O(n) の手法として「Manacher（マナカー）のアルゴリズム」もありますが、理解しやすさという点では、この動的計画法ベースのアプローチが優れた入門例といえます。