Kiểm tra chuỗi là xoay của palindrome trong C++

Kiểm tra một chuỗi có phải là xoay vòng (rotation) của một palindrome hay không. Ví dụ "AAAAD" không phải palindrome nhưng xoay thành "AADAA" là palindrome.

Cách: kiểm tra chuỗi gốc, sau đó xoay trái 1 ký tự, kiểm tra lại, lặp n lần (n = độ dài chuỗi).

Ví dụ

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

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++){
        rotate(str.begin(), str.begin() + 1, str.end());
        if (isPalindromeRange(str, 0, len - 1))
            return true;
    }
    return false;
}

int main(){
    string str = "AAAAD";
    if (isRotatedPalindrome(str))
        cout << "Its rotation is palindrome";
    else
        cout << "Its rotation is not palindrome";
}

Kết quả

Its rotation is palindrome