Effective way to check if a string is a rotary palindrome?

Question

The rotating palindrome is similar to "1234321", "3432112". The naive method will cut the string into different parts and link them back and see if the string is a palindrome. This will 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 am wondering if there is a better solution than this. I think yes, please advice.

Thanks!

Answer 1

According to this wikipedia article, for each row S of length n at time O (n), we can compute an array A of the same size as:

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

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

The algorithm should be found in:

Manacher, Glenn (1975), "New linear" on-line "algorithm for finding the smallest initial string palindrome"

In other words, we can check which line prefixes 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 (empty string or single letter), "p" and "s" are (possibly empty) strings, and "s ^ R" means "s" string reverse.

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

• sxs ^ Rp ^ Rp
• p ^ Rpsxs ^ R

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

As can be seen, the substrings "p ^ Rp" and "sxs ^ R" are palindromes, one of which is of even length, and the other is of odd length if S is of odd length.

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

---

One remark on the solution using rks, this solution does not work, because for line S = 1121 it will create line 11211121, which has a palindrome longer than or equal to length S, but is not a rotary palindrome. If we change the solution so that it checks if a palindrome of length equal to length S exists, this will work, but I don’t see a direct solution how to change the search algorithm for the longest substring so that it will look for a substring of a fixed length (len ( S)). (I did not write this as a comment in the solution, since I am new to Stackoverflow and do not have a sufficient reputation for this)

---

Second remark - I am sorry that I did not include the Manacher algorithm, if someone has a link to the idea of ​​the algorithm or some implementation, please include it in the comments.

Answer 2

Combine the line into yourself, then do a classic palindrome study on a new line. If you find a palindrome that is longer than or equal to the length of the original string, you know that your string is a rotatable palindrome.

As an example, you would do your research in 34321123432112 , finding 21123432112 , the length of which is longer than your starting line, so it rotates the palindrome.

EDIT: as Richard Stefanets noted, my algorithm fails at 1121 , he suggested changing the test >= in length to = .

EDIT2: It should be noted that finding a palindrome of a given size is obviously not easy. Read the discussion in Richard Stefanek's post for more information.

Answer 3

I would like to offer one simple solution using only conventional algorithms. This will not solve any difficult problem, but that should be enough for your task. This is somewhat similar to the other two proposed solutions, but not one of them seems to be concise enough for me to read it carefully.

The first step: combine the string into itself ( abvc → abvcabvc ), as in all other proposed solutions.

Second step: make a preliminary calculation of Rabin-Karp (which uses a sliding hash) on the newly received line and vice versa.

Third step:. Let the string be a length n . For each index i at 0...n-1 check whether the substring of the doubled string [i, i + n - 1] palindrome in constant time using Rabin-Karp preliminary calculations (basically the obtained value for the substring in the forward and reverse direction should be equal).

Conclusion: if any palindrome is found in the third step, then the line will be rotated by the palindrome. If not, then this is not so.

PS: Rabin Karp uses hashes, and collisions are possible even for mismatched strings. Thus, it is a good idea to check the brute force check for equality if it is caused by hash checks. However, if the hash functions used in Rabin Karp are good, the amortized solution speed should remain O(n) .

Answer 4

you can add the same template at the end of the original template. For example, pattern 1234321, then you can add the same pattern at the end of 12343211234321. After that, you can use KMP or other substring matching algorithms to find the string you want. if coincidence, return.