C++で文字列内のすべての回文部分列を数える方法

このチュートリアルでは、与えられた文字列の中に含まれる回文部分列の総数を求めるプログラムについて解説します。

入力として1つの文字列が与えられ、その文字列から作り出せる回文部分列がいくつあるかを数えるのが課題です。

回文部分列とは?

部分列(subsequence)とは、元の文字列から0個以上の文字を削除し、残りの文字の順序を保ったまま作られる文字列のことです。このうち、前から読んでも後ろから読んでも同じになるものを回文部分列と呼びます。

例として、文字列「abcb」を考えてみましょう。この文字列には次の6つの回文部分列が存在します。

• a
• b(先頭)
• c
• b(末尾)
• bb(先頭と末尾のb)
• bcb

アルゴリズムの考え方(動的計画法)

この問題は動的計画法(DP)を用いることで効率的に解くことができます。2次元配列 cps[i][j] を用意し、「部分文字列 str[i..j] 内に含まれる回文部分列の個数」を格納していきます。

漸化式

• 長さ1の部分文字列(1文字)は必ず回文になるため、cps[i][i] = 1
• str[i] == str[k] の場合:cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1(両端の文字を使うことで新たな回文が +1 増える)
• str[i] != str[k] の場合:cps[i][k] = cps[i][k-1] + cps[i+1][k] - cps[i+1][k-1](重複して数えた分を引き算して調整)

区間の長さを2からNへと順番に広げながら表を埋めていき、最終的な答えは cps[0][N-1] となります。計算量は時間・空間ともに O(N²) です。

C++での実装例

#include<iostream>
#include<cstring>
using namespace std;
// 回文部分列の総数を返す関数
int count_palin(string str){
    int N = str.length();
    // 結果を格納する2次元配列
    int cps[N+1][N+1];
    memset(cps, 0 ,sizeof(cps));
    for (int i=0; i<N; i++)
        cps[i][i] = 1;
    for (int L=2; L<=N; L++){
        for (int i=0; i<N; i++){
            int k = L+i-1;
            if (str[i] == str[k])
                cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;
            else
                cps[i][k] = cps[i][k-1] + cps[i+1][k] - cps[i+1][k-1];
        }
    }
    return cps[0][N-1];
}
int main(){
    string str = "abcb";
    cout << "Total palindromic subsequence are : " << count_palin(str) << endl;
    return 0;
}

実行結果

Total palindromic subsequence are : 6

文字列「abcb」に対して、回文部分列の総数である「6」が正しく出力されました。