Using the KMP algorithm, give an O(n) time algorithm(in pseudocode) that, given a string X = a1 . . . an where n is odd, determines whether there is a circular rotation of X that turns it into a palindrome.

For example, if X = CARRACE, the answer is Yes because a left circular rotation of X by three turns it into the palindrome RACECAR