C++で繰り返し文字列内の文字を比較するクエリ処理を実装する方法

この記事では、文字列 str と、2つの値 a と b のペアからなる Q 個のクエリが与えられたとき、「無限に繰り返される文字列」として扱った場合に指定位置の文字同士が一致しているかどうかを判定するプログラムを、C++ で作成する方法を解説します。

問題の概要

各クエリに対して、指定された2つのインデックス a と b における文字が同じであるかを確認し、その結果を返す必要があります。重要なポイントは、与えられた文字列が無限に繰り返されるものとして扱う点です。そのため、インデックスが文字列の長さを超えている場合でも、正しく対応する文字と比較できるようにしなければなりません。

具体例で確認してみましょう。

• 入力： str = "tutorialspoint"
• クエリ数 Q： 2
• クエリ： {{0, 2}, {4, 7}}
• 出力： Repeated / Not Repeated

出力の説明

クエリ1（{0, 2}）： インデックス0の文字は「t」、インデックス2の文字も「t」であり、両者は同じ文字です。よって「Repeated」と判定されます。

クエリ2（{4, 7}）： インデックス4の文字は「r」、インデックス7の文字は「l」であり、これらは異なる文字です。よって「Not Repeated」と判定されます。

解法のアプローチ

この問題の解き方はシンプルです。まず、インデックス a と b にある文字が等しいかどうかを比較します。ただし、インデックスが文字列の長さ（len）を超えている場合は、index % len を計算することで、実際に参照すべき文字の位置を求めます。こうして得られた新しいインデックスを使って比較を行うことで、文字列が何度繰り返されていても正しく判定できます。

この手法が有効なのは、モジュロ演算（剰余演算）を利用することで、仮想的に無限に続く文字列上の任意の位置を、元の文字列の範囲内のインデックスへ一意にマッピングできるためです。これにより、1クエリあたり O(1) の計算量で高速に処理でき、大量のクエリにも柔軟に対応できます。

実装例（サンプルコード）

#include <iostream>
#include <string>
using namespace std;
bool isrepeated(string str, int len, int a, int b){
    if(a > len)
        a %= len;
    if(b > len)
        b %= len;
    if(str[a] == str[b])
        return true;
    else
       return false;
}
int main(){
    string str = "tutorialspoint";
    int len = str.length();
    int Q = 3;
    int query[Q][2] = {{0, 2}, {3, 32}, {5, 18}};
    for(int i = 0; i < Q; i++){
        if(isrepeated(str, len, query[i][0], query[i][1]))
            cout<<"Character is repeated in both the index values"<<endl;
        else
            cout<<"Character is not repeated in both the index values"<<endl;
    }
    return 0;
}

実行結果

Character is repeated in both the index values
Character is not repeated in both the index values
Character is not repeated in both the index values

まとめ

本記事では、繰り返される文字列内の指定された2つの位置の文字を比較するクエリ処理を C++ で実装しました。剰余演算を活用して文字列長を超えるインデックスを範囲内に収めることで、簡潔かつ効率的に一致判定が行えます。このアプローチは、循環するパターンを持つ文字列処理全般に応用できる便利なテクニックなので、ぜひ覚えておきましょう。