Kiểm tra xem một chuỗi đã cho có phải là một vòng quay của palindrome trong C ++ hay không

Ở đây chúng ta sẽ thấy, một chuỗi có phải là palindrome sau khi quay nhất định hay không. Palindrome là một chuỗi giống nhau theo cả hai hướng. Một vòng quay chuỗi là một palindrome nếu nó giống như AAAAD. đây không phải là một palindrome trực tiếp, nhưng AADAA xoay vòng của nó là một palindrome.

Để kiểm tra một chuỗi có được xoay palindrome hay không, lúc đầu chúng ta sẽ kiểm tra xem đây có phải là palindrome hay không, sau đó xoay nó theo một ký tự, sau đó kiểm tra lại, việc kiểm tra này sẽ được thực hiện trong khoảng thời gian n là số ký tự.

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)) //if rotated string is palindrome, then return true
         return true;
   }
   return false;
}
int main(){
   string str = "AAAAD"; //AADAA is palindrome
   //rotate(str.begin(), str.begin() + 2, str.end());
   if (isRotatedPalindrome(str))
      cout << "Its rotation is palindrome";
   else
      cout << "Its rotation is not palindrome";
}

Đầu ra

Its rotation is palindrome