C++で部分文字列[L…R]が回文かどうかを判定するクエリ処理プログラム

この記事では、文字列 str と、それぞれ2つの値 L と R から構成される Q 個のクエリが与えられたとき、各クエリに対して部分文字列 [L…R] が回文（前から読んでも後ろから読んでも同じ文字列）であるかどうかを判定するプログラムを C++ で作成する方法を解説します。

問題の概要

各クエリを処理する際には、指定された範囲 L から R までで切り出した部分文字列が回文であるかどうかを確認する必要があります。

具体例で問題を理解しよう

入力

str = "abccbeba" , Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}}

出力

Palindrome
Not Palindrome
Palindrome

説明

Substring[1...4] = "bccb" → 回文である
Substring[0...6] = "abccbeb" → 回文ではない
Substring[4...6] = "beb" → 回文である

解法アプローチ①：単純な解法（ナイーブな方法）

最もシンプルな解決策は、各クエリをその都度処理することです。つまり、インデックス L から R の範囲で部分文字列を実際に切り出し、その部分文字列が回文かどうかを先頭と末尾を比較しながら確認します。

実装例

#include <bits/stdc++.h>
using namespace std;
int isPallindrome(string str){
    int i, length;
    int flag = 0;
    length = str.length();
    for(i=0;i < length ;i++){
        if(str[i] != str[length-i-1]) {
            flag = 1; break;
        }
    }
    if (flag==1)
        return 1;
        return 0;
}
void solveAllQueries(string str, int Q, int query[][2]){
    for(int i = 0; i < Q; i++){ isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))?cout<<"Palindrome\n":cout<<"Not palindrome!\n";
}
int main() {
    string str = "abccbeba"; int Q = 3;
    int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
    solveAllQueries(str, Q, query);
    return 0;
}

出力

Palindrome
Not palindrome!
Palindrome

この方法は直感的で分かりやすいですが、クエリごとに毎回 O(R−L) の計算が必要となるため、文字列が長い場合やクエリ数が多い場合には非効率です。

解法アプローチ②：動的計画法（DP）を用いた効率的な解法

より効率的な解決策は、動的計画法を利用することです。あらかじめ2次元の DP 配列を作成し、DP[i][j] には「部分文字列 [i…j] が回文であるかどうか」を表す真偽値を格納しておきます。

この DP テーブルを事前に構築しておけば、以降の各クエリは DP テーブルを参照するだけで O(1) で回答できるようになります。

DP テーブルは次のように構成されます：

• 長さ1の部分文字列は常に回文
• 長さ2の部分文字列は、両端の文字が一致すれば回文
• それより長い部分文字列は、「両端の文字が一致し、かつ内側の部分文字列 DP[i+1][j-1] が回文」であれば回文

実装例

#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str){
    int length = str.size();
    int i, j;
    for (i = 0; i < length; i++) {
        for (j = 0; j < length; j++)
            DP[i][j] = 0;
    }
    for (j = 1; j <= length; j++) {
        for (i = 0; i <= length - j; i++) {
            if (j <= 2) {
                if (str[i] == str[i + j - 1])
                    DP[i][i + j - 1] = 1;
            }
            else if (str[i] == str[i + j - 1])
                DP[i][i + j - 1] = DP[i + 1][i + j - 2];
        }
    }
}
void solveAllQueries(string str, int Q, int query[][2]){
    int DP[50][50];
    computeDP(DP, str);
    for(int i = 0; i < Q; i++){
        DP[query[i][0] - 1][query[i][1] - 1]?cout<<"not palindrome!\n":cout<<"palindrome!\n";
    }
}
int main() {
    string str = "abccbeba"; int Q = 3;
    int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
    solveAllQueries(str, Q, query);
    return 0;
}

出力

palindrome!
not palindrome!
palindrome!

まとめ

このように、クエリの数が多い場合は、動的計画法によって前処理を行っておくことで、各クエリへの回答を高速化できます。文字列の長さとクエリ数のバランスを考慮して、適切な手法を選択することが重要です。