## Rotated Palindrome

### December 15, 2017

Today’s exercise provides simple finger exercise for a Friday morning:

A palindrome is a string that reads the same forward and backward; for instance “abcdedcba” is a palindrome. A rotated palindrome is a string that reads the same forward and backward, either directly or in any rotation of the string; for instance, “dedcbaabc” is a rotated palindrome, because if the last three letters at the end of the string are rotated to the beginning of the string, it becomes “abcdedcba” which is a palindrome.

Your task is to write a program to determine if a string is a rotated palindrome. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

An observation: the rotation of a palindromic string is of the form B X B’ A’ A or A’ A B X B’, where A’, B’ is the reverse of A, B and any of A, B or X might be empty.

Another observation: if S’ is a substring of S S, then S must be of the form A B where A = A’ and B = B’

Here’s some code: match reverse string as above, then each part of even length can be wrapped around the other part to get a palindrome:

Here’s a solution in C99.

Output:

In Python

A Haskell version. The isPalindrome function is arguably a little too cute, but it’s a clever use of the Monad instance of lists I once saw on Reddit.

My solution above can run in O(n) time, using a suitable string find algorithm such as Knuth-Morris-Pratt. I wonder if there is a way to use the KMP tables more directly to solve the problem.

One-liner in Python. It basically says is there any possible middle point of the string for which all index left/right are equal. Python support negative indexing, so no need to ‘rotate’ the string yourself.

@Rutger: neat, but seems to only work for odd-length strings.

asd

Here is the solution is

`QBasic`

Here is java 8 solution

Here’s a version of Rutger’s solution that handles the even-length case. Not quite a one-liner, but short enough. Also a little test function, comparing the new function with findpals from above:

Season’s greetings to all.