最長回文部分列（Longest Palindromic Subsequence）の求め方｜動的計画法で解く

最長回文部分列とは

最長回文部分列（Longest Palindromic Subsequence）とは、与えられた文字列から一部の文字を選んで並べた「部分列」のうち、前から読んでも後ろから読んでも同じになる（回文となる）ものの中で、最も長いものを指します。

この問題では、1つの文字列が与えられたとき、そこから作れる最長の回文部分列の長さを求めます。

解法の考え方：漸化式

この問題は動的計画法（DP）を使うことで効率よく解けます。基本となる漸化式は次のとおりです。

L(0, n-1) を文字列全体に対する最長回文部分列の長さとすると、
L(0, n-1) = L(1, n-2) + 2　※0番目と (n-1) 番目の文字が一致する場合

つまり、両端の文字が一致していれば、その内側の区間の答えに 2 を加えることで解が得られます。一致しない場合は、片側を縮めた2つの区間のうち大きい方を採用します。

入力と出力

入力：
さまざまな文字や記号を含む文字列。例として「ABCDEEAB」を入力する。
出力：
最長の回文部分列の長さ。この場合は 4。
ABCDEEAB → 回文は「AEEA」（長さ4）

アルゴリズム

palSubSeqLen(str)

入力 − 与えられた文字列

出力 − 最長回文部分列の長さ

Begin
    n := 文字列の長さ
    n × n のサイズの表 lenTable を作成し、すべて 1 で初期化する
    for col := 2 to n, do
        for i := 0 to n – col, do
            j := i + col – 1
            if str[i] = str[j] かつ col = 2, then
                lenTable[i, j] := 2
            else if str[i] = str[j], then
                lenTable[i, j] := lenTable[i+1, j-1] + 2
            else
                lenTable[i, j] := lenTable[i, j-1] と lenTable[i+1, j] の最大値
        done
    done
    return lenTable[0, n-1]
End

ここで lenTable[i][j] は「i番目からj番目までの部分文字列における最長回文部分列の長さ」を表します。長さ1の文字列はそれ自体が回文であるため、対角成分はすべて 1 で初期化されます。

C++での実装例

#include<iostream>
using namespace std;

int max (int x, int y) {
    return (x > y)? x : y;
}

int palSubseqLen(string str) {
    int n = str.size();
    int lenTable[n][n];              // 部分問題の結果を格納する表を作成

    for (int i = 0; i < n; i++)
        lenTable[i][i] = 1;          // 長さ1の文字列はそれ自体が回文

    for (int col=2; col<=n; col++) {
        for (int i=0; i<n-col+1; i++) {
            int j = i+col-1;
            if (str[i] == str[j] && col == 2)
                lenTable[i][j] = 2;
            else if (str[i] == str[j])
                lenTable[i][j] = lenTable[i+1][j-1] + 2;
            else
                lenTable[i][j] = max(lenTable[i][j-1], lenTable[i+1][j]);
        }
    }
    return lenTable[0][n-1];
}

int main() {
    string sequence = "ABCDEEAB";
    int n = sequence.size();
    cout << "The length of the longest palindrome subsequence is: " << palSubseqLen(sequence);
}

出力

The length of the longest palindrome subsequence is: 4

計算量について

この動的計画法によるアプローチでは、表の全マスを一度ずつ埋めていくため、時間計算量は O(n²)、使用する表の分だけ空間計算量も O(n²) となります。全ての部分列を総当たりで調べる指数時間の方法と比べ、文字列が長くなっても現実的な時間で解けるのが大きな利点です。