C++による回文分割：最小カット数を求めるアルゴリズム

回文分割とは

入力として与えられた文字列を、分割後のすべての部分文字列が回文になるように分割することを「回文分割（Palindrome Partitioning）」と呼びます。この記事では、与えられた文字列を回文に分割するために必要な最小のカット数を求めるアルゴリズムを解説します。

例として、文字列「ababbbabbababa」を考えてみましょう。この場合、3回のカットで次のように回文へ分割できます。

a | babbbab | b | ababa

アルゴリズムの考え方（動的計画法）

この問題は動的計画法（DP）を用いて効率的に解くことができます。まず、n × n の2次元テーブルを2つ用意します。

• pal[i][j]：部分文字列 str[i..j] が回文であれば true
• cut[i][j]：部分文字列 str[i..j] を回文に分割するために必要な最小カット数

具体的な手順は以下の通りです。

• n := 文字列 str の長さとする
• cut と pal という n × n の行列を定義する
• i = 0 ～ n-1 について、pal[i][i] := true、cut[i][i] := 0 とする（長さ1の部分文字列は常に回文）
• len を 2 ～ n について繰り返す
  • i を 0 ～ n – len について繰り返す
    • j := i + len – 1 とする（部分文字列の終了インデックス）
    • len = 2 の場合：str[i] == str[j] なら pal[i][j] := true
    • それ以外の場合：str[i] == str[j] かつ pal[i+1][j-1] が true なら pal[i][j] := true
    • pal[i][j] が true なら cut[i][j] := 0
    • そうでない場合は以下を実行
      • cut[i][j] := ∞（無限大で初期化）
      • k を i ～ j-1 について繰り返し、cut[i][j] := min(cut[i][j], cut[i][k] + cut[k+1][j] + 1) で更新
• 最後に cut[0][n-1] を返す

C++での実装例

理解を深めるために、以下のC++実装例を見てみましょう。

#include <iostream>
#include <climits>
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]; //true when palindrome present for i to j th element
    for (int i=0; i<n; i++){
        pal[i][i] = true; //substring of length 1 is plaindrome
        cut[i][i] = 0;
    }
    for (int len=2; len<=n; len++){
        for (int i=0; i<n-len+1; i++){//find all substrings of length len
        int j = i+len-1; // Set ending index
        if (len == 2) //for two character string
            pal[i][j] = (str[i] == str[j]);
        else //for string of more than two characters
            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; //initially set as infinity
            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);
}

入力

ababbbabbababa

出力

Min cuts for Palindrome Partitioning is: 3

計算量について

このアルゴリズムの時間計算量は O(n³)、空間計算量は O(n²) です。なお、pal テーブルを先に完成させ、1次元の cut 配列を用いることで、時間計算量を O(n²) まで最適化することも可能です。