C++で回文部分文字列クエリを解く方法：全探索から動的計画法まで

はじめに

本記事では、与えられた文字列に対する「回文部分文字列クエリ」をC++で解く方法を解説します。通常の部分文字列クエリに比べ、回文の判定はコード量もロジックも格段に複雑になります。ここでは、シンプルな全探索（素朴な方法）と、効率的な動的計画法（DP）の2つのアプローチを紹介します。

問題概要

文字列 str と、Q 個のクエリ [L...R] が与えられます。各クエリは2つの整数 L と R を持ち、目的は「範囲 L から R までで形成される部分文字列が回文かどうか」を判定するプログラムを作成することです。具体例を見てみましょう。

入力文字列: "abbbabaaaba"（長さ11）
クエリ: [3, 11], [4, 6], [2, 4], [5, 9]

[3, 11] → "bbabaaaba" … 回文ではない
[4, 6]  → "bab"      … 回文である
[2, 4]  → "bbb"      … 回文である
[5, 9]  → "abaaa"    … 回文ではない

アプローチ1：素朴な方法（全探索）

最も単純な方法は、各クエリごとに実際に部分文字列を切り出し、先頭と末尾を順に比較して回文かどうかを確認するものです。1回の判定に O(N) の時間がかかり、クエリが Q 個あるため、全体の計算量は最悪で O(Q×N) となります。文字列長とクエリ数がどちらも大きい場合には非現実的な速度になります。

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

// 文字列が回文かどうかを判定する
bool isPalindrome(const string& s) {
    int left = 0, right = (int)s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        ++left; --right;
    }
    return true;
}

// すべてのクエリを処理する
void solveAllQueries(const string& str, int Q, const int query[][2]) {
    for (int i = 0; i < Q; ++i) {
        int L = query[i][0] - 1;               // 0始まりのインデックスへ変換
        int R = query[i][1] - 1;
        string sub = str.substr(L, R - L + 1); // 部分文字列を取り出す
        cout << (isPalindrome(sub) ? "Palindrome\n" : "Not palindrome!\n");
    }
}

int main() {
    string str = "abccbeba";
    int Q = 3;
    int query[3][2] = {{3, 5}, {5, 7}, {1, 8}};
    solveAllQueries(str, Q, query);
    return 0;
}

出力

Not palindrome!
Palindrome
Not palindrome!

アプローチ2：動的計画法（DP）

より効率的なのが動的計画法です。dp[i][j] を「部分文字列 str[i...j] が回文であれば true」というブール値として定義し、あらかじめ N×N の表をすべて埋めておきます。こうすれば、各クエリには表を参照するだけで O(1) で答えられます。

漸化式は次の通りです。

• 長さ1の部分文字列は常に回文：dp[i][i] = true
• 長さ2の場合：dp[i][i+1] = (str[i] == str[i+1])
• 長さ3以上の場合：dp[i][j] = (str[i] == str[j]) && dp[i+1][j-1]

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

const int MAXN = 100;
bool dp[MAXN][MAXN];

// dp[i][j] = str[i..j] が回文なら true
void computeDP(const string& str) {
    int n = (int)str.size();

    // 長さ1
    for (int i = 0; i < n; ++i) dp[i][i] = true;

    // 長さ2
    for (int i = 0; i + 1 < n; ++i)
        dp[i][i + 1] = (str[i] == str[i + 1]);

    // 長さ3以上
    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            dp[i][j] = (str[i] == str[j]) && dp[i + 1][j - 1];
        }
    }
}

void solveAllQueries(const string& str, int Q, const int query[][2]) {
    computeDP(str);
    for (int i = 0; i < Q; ++i) {
        int L = query[i][0] - 1;
        int R = query[i][1] - 1;
        cout << (dp[L][R] ? "Palindrome\n" : "Not palindrome!\n");
    }
}

int main() {
    string str = "abccbeba";
    int Q = 3;
    int query[3][2] = {{3, 5}, {5, 7}, {1, 8}};
    solveAllQueries(str, Q, query);
    return 0;
}

出力

Not palindrome!
Palindrome
Not palindrome!

計算量の比較

クエリ数が多い場合は、前処理に時間をかけても各クエリを定数時間で処理できるDPアプローチが圧倒的に有利です。なお、さらに高度な手法として、Manacher（マナカー）のアルゴリズムを使えば O(N) の前処理で同様のクエリに応答できるほか、文字列ハッシュやEertree（回文木）を利用する方法もあります。ただしいずれも実装難度は高くなります。

まとめ

本記事では、C++における回文部分文字列クエリの解き方を、素朴な全探索と動的計画法の2つのアプローチで解説しました。同じロジックはJavaやPythonなど他の言語でも実装可能です。回文クエリは通常の部分文字列クエリよりも難しく、正確なロジックが求められます。入力規模が大きい問題では、前計算によって各クエリを高速に処理するDPアプローチを採用しましょう。本記事が皆さんの学習の一助になれば幸いです。