回文分割アルゴリズム – 最小カット数で文字列を回文に分割する方法

回文分割とは

このアルゴリズムでは、文字列を入力として受け取ります。分割によって得られるすべての部分文字列が回文になっているとき、その分割を「回文分割（Palindrome Partitioning）」と呼びます。

ここで扱う問題は、与えられた文字列を回文だけから構成されるように分割するとき、必要なカット（切り分け）の回数を最小化するというものです。

たとえば「ababbbabbababa」という文字列は、「a | babbbab | b | ababa」のように3回のカットで、回文のみからなる部分文字列に分割できます。

入力と出力

入力:
文字列（例: "ababbbabbababa"）

出力:
回文として分割するための最小カット数。この例では3回のカットが必要。
回文への分割例: a | babbbab | b | ababa

アルゴリズムの考え方

この問題は動的計画法（DP）を用いることで効率的に解くことができます。サイズ n × n の2つの表を用意します。

• pal[i][j]：部分文字列 str[i..j] が回文であるかどうかを記録する表
• cut[i][j]：部分文字列 str[i..j] を回文に分割するために必要な最小カット数を記録する表

まず、長さ1の部分文字列は必ず回文であるため、pal[i][i] = true、cut[i][i] = 0 と初期化します。次に部分文字列の長さを2から順に伸ばしながら pal 表を更新します。両端の文字が一致し（str[i] == str[j]）、かつ内側の部分文字列 pal[i+1][j-1] が回文であれば、pal[i][j] も回文となります。

cut の計算では、pal[i][j] が true ならカット数は0です。そうでなければ、分割位置 k をすべて試し、cut[i][k] + cut[k+1][j] + 1 の最小値を求めます。

擬似コード

minPalPart(str)

入力: 与えられた文字列
出力: 回文分割に必要な最小カット数

Begin
    n := strの長さ
    n × n の cut 行列と pal 行列を定義

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

    for len := 2 to n, do
        for i := 0 to n - len, do
            j := i + len - 1
            if len = 2 then
                if str[i] = str[j] then
                    pal[i, j] := true
            else
                if str[i] = str[j] かつ pal[i+1, j-1] ≠ false then
                    pal[i, j] := true

            if pal[i, j] = true then
                cut[i, j] := 0
            else
                cut[i, j] := ∞
                for k := i to j-1, do
                    cut[i, j] := min(cut[i, j], cut[i, k] + cut[k+1, j] + 1)
                done
        done
    done
    return cut[0, n-1]
End

C++による実装例

#include <iostream>
using namespace std;

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

int minPalPartion(string str) {
    int n = str.size();

    int cut[n][n];
    bool pal[n][n];              // str[i..j] が回文ならtrue

    for (int i=0; i<n; i++) {
        pal[i][i] = true;        // 長さ1の部分文字列は常に回文
        cut[i][i] = 0;
    }

    for (int len=2; len<=n; len++) {
        for (int i=0; i<n-len+1; i++) {   // 長さlenのすべての部分文字列を調べる

            int j = i+len-1;              // 終了インデックスを設定
            if (len == 2)                 // 2文字の文字列の場合
                pal[i][j] = (str[i] == str[j]);
            else                          // 3文字以上の場合
                pal[i][j] = (str[i] == str[j]) && pal[i+1][j-1];

            if (pal[i][j] == true)
                cut[i][j] = 0;
            else {
                cut[i][j] = INT_MAX;      // 初期値は無限大として設定
                for (int k=i; k<=j-1; k++)
                    cut[i][j] = min(cut[i][j], cut[i][k] + cut[k+1][j]+1);
            }
        }
    }
    return cut[0][n-1];
}

int main() {
    string str = "ababbbabbababa";
    cout << "Min cuts for Palindrome Partitioning is:" << minPalPartion(str);
}

実行結果

Min cuts for Palindrome Partitioning is: 3

計算量

• 時間計算量： O(n³) — pal 表の作成に O(n²)、cut の更新には分割位置を試す3重ループが必要なため
• 空間計算量： O(n²) — 2つの n × n の表を保持する必要があるため