C++で特定の文字列が回文の回転であるかどうかを判定する方法

回文の回転とは

回文（パリンドローム）とは、前から読んでも後ろから読んでも同じになる文字列のことです。本記事では、ある文字列が「回文を回転させたもの」になっているかどうかをC++で判定する方法を解説します。

例えば「AAAAD」という文字列は、そのままでは回文ではありません。しかし、これを1文字ずつ回転させていくと「AADAA」となり、これは回文です。このように、元の文字列自体は回文でなくても、適切な位置まで回転させることで回文になるケースが存在します。

判定アルゴリズムの考え方

文字列が回文の回転であるかを確認するには、以下の手順を実行します。

1. まず、現在の文字列が回文かどうかをチェックします。
2. 回文でなければ、文字列を1文字分左に回転させます。
3. 再度回文かどうかをチェックします。
4. この処理を文字数n回繰り返し、1度でも回文になれば「回文の回転」と判定できます。

すべての回転パターンを試しても回文が見つからない場合は、その文字列のどの回転も回文ではないと結論付けられます。計算量は各回転ごとに回文判定にO(n)かかるため、全体でO(n²)となります。

C++による実装例

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 指定範囲[left, right]が回文かどうかを再帰的に判定する関数
bool isPalindromeRange(string str, int left, int right){
    return (left >= right) || (str[left] == str[right] && isPalindromeRange(str, left + 1, right - 1));
}

// 回転を繰り返しながら回文判定を行う関数
bool isRotatedPalindrome(string str){
    int len = str.length();
    for (int i = 0; i < len; i++){
        // 1文字分だけ左へ回転
        rotate(str.begin(), str.begin() + 1, str.end());
        if (isPalindromeRange(str, 0, len - 1)) // 回転後の文字列が回文ならtrueを返す
            return true;
    }
    return false;
}

int main(){
    string str = "AAAAD"; // 「AADAA」が回文になる
    if (isRotatedPalindrome(str))
        cout << "Its rotation is palindrome";
    else
        cout << "Its rotation is not palindrome";
}

実行結果

Its rotation is palindrome

このプログラムでは、STLのrotate関数を使って文字列を1文字ずつ回転させながら、再帰的な回文判定関数isPalindromeRangeで全パターンをチェックしています。「AAAAD」の場合、2回目の回転で「AADAA」となり回文が見つかるため、「Its rotation is palindrome（その回転は回文である）」と出力されます。