## Rotated Palindrome

### December 15, 2017

We begin by writing two utility functions on strings; `string-reverse`

reverses the characters in a string, and `string-rotate`

moves *n* characters from the front of a string to the back. Both functions work by converting the strings to lists of characters, then calling functions on lists to perform the conversion, finally converting the lists back to strings:

(define (string-reverse str) (list->string (reverse (string->list str))))

(define (string-rotate n str) (call-with-values (lambda () (split n (string->list str))) (lambda (front back) (list->string (append back front)))))

Then it is easy to check if a string is a rotated palindrome by rotating the string one character at a time, checking each rotation to see if it is a palindrome:

(define (rot-pal? str) (let loop ((n (string-length str)) (str str)) (if (zero? n) #f (if (string=? str (string-reverse str)) #t (loop (- n 1) (string-rotate 1 str))))))

You can run the program at https://ideone.com/DqWBKA.

Advertisements

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.