C++で文字列のすべての回文分割（パリンドロームパーティション）を出力する方法

問題の概要

この問題では、回文（パリンドローム）となる文字列が与えられ、その文字列を切り分けることで得られるすべての可能な回文分割（パーティション）を出力する必要があります。

具体例を見てみましょう。

入力: string = 'ababa'
出力: ababa、a bab a、a b a b a など

このように、同じ文字列でも切り分け方によって複数の回文分割パターンが存在します。

解決のアプローチ

この問題を解く基本的な考え方は、文字列の各部分文字列が回文であるかどうかを順番にチェックすることです。部分文字列が回文であれば、それを現在の分割リストに追加し、残りの部分に対して再帰的に同じ処理を繰り返します。この手法はバックトラッキングと呼ばれるアルゴリズム手法を用いており、すべての分割パターンを網羅的に探索できます。

C++での実装例

以下のプログラムは、この問題の解法を示しています。

#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(string str, int low, int high){
    while (low < high) {
        if (str[low] != str[high])
            return false;
        low++;
        high--;
    }
    return true;
}
void palindromePartition(vector<vector<string> >&allPart, vector<string> &currPart, int start, int n, string str){
    if (start >= n) {
        allPart.push_back(currPart);
        return;
    }
    for (int i=start; i<n; i++){
        if (isPalindrome(str, start, i)) {
            currPart.push_back(str.substr(start, i-start+1));
            palindromePartition(allPart, currPart, i+1, n, str);
            currPart.pop_back();
        }
    }
}
void generatePalindromePartitions(string str){
    int n = str.length();
    vector<vector<string> > partitions;
    vector<string> currPart;
    palindromePartition(partitions, currPart, 0, n, str);
    for (int i=0; i< partitions.size(); i++ ) {
        for (int j=0; j<partitions[i].size(); j++)
            cout<<partitions[i][j]<<" ";
        cout<<endl;
    }
}
int main() {
    string str = "abaaba";
    cout<<"Palindromic partitions are :\n";
    generatePalindromePartitions(str);
    return 0;
}

出力結果

Palindromic partitions are :
a b a a b a
a b a aba
a b aa b a
a baab a
aba a b a
aba aba
abaaba

アルゴリズムのポイント

• isPalindrome関数: 2つのインデックス（lowとhigh）を両端から中央に向かって移動させながら文字を比較し、部分文字列が回文かどうかを判定します。
• palindromePartition関数: 開始位置から順に部分文字列を切り出し、回文であれば現在の分割リストに追加して、残りの部分を再帰的に処理します。
• バックトラッキング: 再帰呼び出しの後にpop_back()を呼び出すことで、直前に追加した部分文字列を取り除き、別の切り分けパターンを探索できるようにします。
• 終了条件: 開始位置が文字列の長さ以上になった時点で、1つの完全な分割パターンが完成したことになるため、結果リストに保存します。

この実装により、文字列「abaaba」に対して7通りの回文分割パターンがすべて出力されます。計算量は最悪の場合O(2ⁿ)となりますが、回文判定を事前に計算する動的計画法（DP）と組み合わせることで、効率をさらに改善することも可能です。