C++で文字置換クエリ実行後に回文かどうかを判定する方法

文字列と、クエリの集合Qが与えられている状況を考えてみましょう。各クエリは2つの整数 i と j、および1つの文字 c から構成されます。クエリが実行されると、文字列のインデックス i と j にある文字が新しい文字 c に置き換えられ、その結果の文字列が回文（前から読んでも後ろから読んでも同じになる文字列）であるかどうかを判定する必要があります。

例えば、「AXCDCMP」という文字列に対してクエリ (1, 5, 'B') を適用すると、文字列は「ABCDCBP」になります。続けて別のクエリ (0, 6, 'A') を適用すると、文字列は「ABCDCBA」となり、これは回文です。

アルゴリズムの流れ

1. クエリに含まれるインデックス i と j を取得し、文字列の該当位置にある文字を文字 c で置き換えます。
2. 置き換え後の文字列について、先頭と末尾から順に文字を比較し、回文であるかどうかを判定します。
3. 各クエリの処理後に判定結果を出力します。

C++による実装例

#include <iostream>
using namespace std;

class Query{
    public:
    int i, j;
    char c;
    Query(int i, int j, char c){
        this->i = i;
        this->j = j;
        this->c = c;
    }
};

bool isPalindrome(string str){
    int n = str.length();
    for (int i = 0; i < n/2 ; i++)
    if (str[i] != str[n-1-i])
        return false;
    return true;
}

bool palindromeAfterQuerying(string str, Query q[], int n){
    for(int i = 0; i<n; i++){
        str[q[i].i] = q[i].c;
        str[q[i].j] = q[i].c;
        if(isPalindrome(str)){
            cout << str << " is Palindrome"<< endl;
        }else{
            cout << str << " is not Palindrome"<< endl;
        }
    }
}

int main() {
    Query q[] = {{1, 5, 'B'}, {0, 6, 'A'}};
    int n = 2;
    string str = "AXCDCMP";
    palindromeAfterQuerying(str, q, n);
}

出力結果

ABCDCBP is not Palindrome
ABCDCBA is Palindrome

コードの解説

Queryクラス： 各クエリの情報（インデックス i、j および置き換え後の文字 c）を保持するためのクラスです。コンストラクタでメンバ変数を初期化しています。

isPalindrome関数： 文字列の長さの半分までループを回し、対称位置にある文字同士を比較します。1つでも異なる文字があれば false を返し、すべて一致すれば true を返します。

palindromeAfterQuerying関数： すべてのクエリを順番に処理します。各クエリで指定されたインデックスの文字を置き換えた後、isPalindrome関数を呼び出して回文判定を行い、その結果を出力します。

計算量

各クエリにおける文字の置換は O(1)、回文判定は文字列の長さを N とすると O(N) で行われます。したがって、クエリ数を Q とすると、全体の計算量は O(Q × N) となります。文字列が長くクエリが多い場合には、より効率的なデータ構造を検討する価値があります。