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

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

文字列が与えられ、その中に含まれる回文部分文字列のうち、長さが2以上のものを数えるのが課題です。単一の文字も回文とみなせますが、この実装では2文字以上の回文を対象としています。

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

この問題は動的計画法(DP)を用いることで効率的に解くことができます。ここでは2つの2次元配列を使用します。

• P[i][j]:部分文字列 str[i..j] が回文であれば true となる真偽値テーブル
• dp[i][j]:部分文字列 str[i..j] に含まれる回文部分文字列の個数

まず、長さ1の部分文字列はすべて回文であるため P[i][i] = true と初期化します。次に、隣接する2文字が等しい場合、その長さ2の部分文字列は回文となるので P[i][i+1] = true とし、dp[i][i+1] = 1 とします。

それより長い部分文字列については、「両端の文字が一致し、かつその内側の部分文字列が回文である」ときに回文と判定できます。回文の個数は、すでに計算済みの隣接区間の値を組み合わせた漸化式によって求めます。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
//回文部分文字列を数える関数
int count_pstr(char str[], int n){
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    bool P[n][n];
    memset(P, false , sizeof(P));
    for (int i= 0; i< n; i++)
        P[i][i] = true;
    for (int i=0; i<n-1; i++) {
        if (str[i] == str[i+1]) {
            P[i][i+1] = true;
            dp[i][i+1] = 1 ;
        }
    }
    for (int gap=2 ; gap<n; gap++) {
        for (int i=0; i<n-gap; i++) {
            int j = gap + i;
            //現在の部分文字列が回文である場合
            if (str[i] == str[j] && P[i+1][j-1] )
                P[i][j] = true;
            if (P[i][j] == true)
                dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];
            else
                dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
        }
    }
    return dp[0][n-1];
}
int main(){
    char str[] = "abaab";
    int n = strlen(str);
    cout << count_pstr(str, n) << endl;
    return 0;
}

実行結果

3

コードの解説

入力文字列は 「abaab」 です。この文字列に含まれる長さ2以上の回文部分文字列は「aa」「aba」「baab」の3つであるため、出力は 3 になります。

このアルゴリズムでは、部分文字列の長さ(gap)を1ずつ増やしながらすべての区間を調べるため、時間計算量は O(n²)、空間計算量も O(n²) となります。文字列の長さがそれほど大きくない場合に有効な手法です。