各部分文字列が回文になるように文字列を分割する方法をすべて求めるC++プログラム

本記事では、与えられた文字列を「すべての部分文字列が回文(前から読んでも後ろから読んでも同じになる文字列)」となるように分割する方法をすべて列挙するC++プログラムを紹介します。たとえば「tutorials」という文字列なら、1文字ずつに分割する方法や、先頭の「tut」をひとまとまりにして残りを1文字ずつにする方法などが該当します。

アルゴリズム

処理の基本的な流れは次のとおりです。

Begin
    文字列を入力として受け取る。
    関数 partitionadd(vector<vector<string>> &u, string &s, vector<string> &tmp, int index):
        if (index == 0)
            tmp.clear()
        for i = index to length-1
            st = st + s[i]
            if (checkPalin(st))
                tmp.push_back(st)
                if (i+1 < length)
                    partitionadd(u, s, tmp, i+1)
                else
                    u.push_back(tmp)
                tmp = curr
        return
End
Begin
    関数 partition(string st, vector<vector<string>> &u):
        vector<string> tmp
        partitionadd(u, st, tmp, 0)
        printSol(u)  // 解を出力する
    return
End

サンプルコード

#include <bits/stdc++.h>
using namespace std;

// 文字列が回文かどうかを判定する関数
bool checkPalin(string s) {
    int length = s.length();
    length--;
    for (int i = 0; i < length; i++) {
        if (s[i] != s[length])
            return false;
        length--;
    }
    return true;
}

// 求めた分割結果を出力する関数
void printSol(vector<vector<string>> part) {
    for (int i = 0; i < part.size(); ++i) {
        for (int j = 0; j < part[i].size(); ++j)
            cout << part[i][j] << " ";
        cout << endl;
    }
    return;
}

// 回文となる分割を再帰的に探索する関数
void partitionadd(vector<vector<string>> &u, string &s, vector<string> &tmp, int index) {
    int length = s.length(); // 文字列の長さを保持
    string st;
    vector<string> curr = tmp;
    if (index == 0)
        tmp.clear();
    // すべてのインデックスを走査し、現在の部分文字列が回文なら残りの分割を再帰的に追加する
    for (int i = index; i < length; ++i) {
        st = st + s[i];
        if (checkPalin(st)) {
            tmp.push_back(st);
            if (i + 1 < length)
                partitionadd(u, s, tmp, i + 1);
            else
                u.push_back(tmp);
            tmp = curr; // バックトラックして別のパターンを試す
        }
    }
    return;
}

// 文字列stのすべての回文分割を生成し、結果をuに格納する
void partition(string st, vector<vector<string>> &u) {
    vector<string> tmp;
    partitionadd(u, st, tmp, 0);
    printSol(u); // 解を出力
    return;
}

int main() {
    string s = "tutorials";
    vector<vector<string>> part;
    cout << "the number of partitions:" << endl;
    partition(s, part);
    return 0;
}

実行結果

the number of partitions:
t u t o r i a l s
tut o r i a l s

プログラムの解説

• checkPalin関数: 引数に渡された文字列が回文かどうかを判定します。先頭と末尾から順に文字を比較していき、一致しない文字が見つかった時点でfalseを返します。
• partitionadd関数: 再帰呼び出しとバックトラッキングを組み合わせて、可能なすべての回文分割を探索します。index以降の部分文字列が回文であれば一時リストtmpに追加し、文字列の終端まで到達したら完成した分割を結果uに格納します。探索後はtmpを元の状態に戻すことで、別の分割パターンも漏れなく試せる仕組みです。
• 計算量について: 分割パターンの総数は文字列長に対して指数的に増加しうるため、最悪時の計算量はO(n×2ⁿ)程度になります。そのため、この手法は比較的短い文字列に適しています。