Efficient way to verify if a string is a rotated palindrome?

Question

A rotated palindrome is like "1234321", "3432112". The naive method will be cut the string into different pieces and concate them back and see if the string is a palindrome. That would take O(n^2) since there are n cuts and for each cut we need O(n) to check if the string is a palindrome. I'm wondering if there's a better solution than this. I guess so, please advice.

Thanks!

Answer 1

According to this wikipedia article it is possible for each string S of length n in time O(n) compute an array A of the same size, such that:

A[i]==1 iff the prefix of S of length i is a palindrome.

http://en.wikipedia.org/wiki/Longest_palindromic_substring

The algorithm should be possible to find in:

Manacher, Glenn (1975), "A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string"

In other words we can check which prefixes of the string are palindromes in linear time. We will use this result to solve the proposed problem.

Each (non-rotating) palindrome S has the following form S = psxs^Rp^R.

Where "x" is the center of the palindrome (either empty string or one letter string), "p" and "s" are (possibly empty) strings and "s^R" means "s" string reversed.

Each rotating palindrome created from this string has one of the two following forms (for some p):

1. sxs^Rp^Rp
2. p^Rpsxs^R

This is true, because you can choose if to cut some substring before or after the middle of the palindrome and then paste it on the other end.

As one can see the substrings "p^Rp" and "sxs^R" are both palindromes, one of then of even length and the other on odd length iff S is of odd length.

We can use the algorithm mentioned in the wikipedia link to create two arrays A and B. The array A is created by checking which prefixes are palindromes and B for suffixes. Then we search for a value i such that A[i]==B[i]==1 such that either prefix or suffix has even length. We will find such index iff the proposed string is a rotated palindrome and the even part is the "p^Rp" substring, so we can easily recover the original palindrome by moving half of this string to the other end of the string.

---

One remark to the solution by rks, this solution doesn't work, as for a string S = 1121 it will create string 11211121 which has palindrome of length longer or equal than the length of S, but it is not a rotated palindrome. If we change the solution such that it checks whether there exist a palindrome of length equal to length of S, it would work, but i don't see any direct solution how to change the algorithm searching for longest substring in such a way that it would search for substring of fixed length (len(S)). (i didn't write this as a comment under the solution as i'm new to Stackoverflow and don't have enough reputation to do so)

---

Second remark -- I'm sorry not to include the algorithm of Manacher, if someone has link to either the idea of the algorithm or some implementation please include it in the comments.

Answer 2

Concatenate the string to itself, then do the classical palindrome research in the new string. If you find a palindrome whose length is longer or equal to the length of your original string, you know your string is a rotated palindrome.

For your example, you would do your research in 34321123432112 , finding 21123432112, which is longer than your initial string, so it's a rotated palindrome.

EDIT: as Richard Stefanec noted, my algorithm fails on 1121, he proposed that we change the >= test on the length by =.

EDIT2: it should be noted than finding a palindrome of a given size isn't obviously easy. Read the discussion under Richard Stefanec post for more information.

Answer 3

#Given a string, check if it is a rotation of a palindrome. 
#For example your function should return true for “aab” as it is a rotation of “aba”.
string1 = input("Enter the first string")
def check_palindrome(string1):
    #string1_list = [word1 for word1 in string1]
    #print(string1_list)
    string1_rotated = string1[1::1] + string1[0]
    print(string1_rotated)
    string1_rotated_palindrome = string1_rotated[-1::-1]
    print(string1_rotated_palindrome)
    if string1_rotated == string1_rotated_palindrome:
        return True
    else:
        return False
isPalindrome = check_palindrome(string1)
if(isPalindrome):
    print("Rotated string is palindrome as well")
else:
    print("Rotated string is not palindrome")