验证字符串是否为旋转回文的有效方法? [英] Efficient way to verify if a string is a rotated palindrome?
问题描述
旋转回文就像"1234321"，"3432112". 天真的方法会将字符串切成不同的片段，然后将它们重新连接起来，看看字符串是否是回文. 这将需要O(n ^ 2)，因为有n个剪切，对于每个剪切，我们需要O(n)来检查字符串是否是回文. 我想知道是否有比这更好的解决方案. 我想是的，请指教.
谢谢！
根据此Wikipedia文章，对于时间为n的每个长度为S的字符串S，都有可能在O(n)中计算相同大小的数组A，从而:
A [i] == 1，如果长度为i的S的前缀是回文.
http://en.wikipedia.org/wiki/Longest_palindromic_substring
该算法应该可以在以下位置找到:
Manacher，Glenn(1975)，一种新的线性时间在线"算法，用于 找到一个字符串的最小初始回文."
换句话说，我们可以检查字符串中哪些前缀是线性时间中的回文.我们将使用这个结果来解决所提出的问题.
每个回旋回文S具有以下形式S = psxs ^ Rp ^ R.
其中"x"是回文的中心(空字符串或一个字母字符串)， "p"和"s"是(可能为空)字符串，"s ^ R"表示"s"字符串颠倒.
由此字符串创建的每个旋转回文具有以下两种形式之一(对于某些p):
- sxs ^ Rp ^ Rp
- p ^ Rpsxs ^ R
这是正确的，因为您可以选择在回文的中间之前还是之后剪切一些子字符串，然后将其粘贴到另一端.
正如人们所看到的那样，子字符串"p ^ Rp"和"sxs ^ R"都是回文，其中一个是偶数长度，另一个在奇数长度iff S上是奇数长度.
我们可以使用Wikipedia链接中提到的算法来创建两个数组A和B.通过检查哪些前缀是回文前缀和B作为后缀来创建数组A.然后，我们搜索一个值i，使得A [i] == B [i] == 1使得前缀或后缀具有偶数长度.如果建议的字符串是旋转回文，而偶数部分是"p ^ Rp"子字符串，我们会找到这样的索引，因此，我们可以通过将字符串的一半移到字符串的另一端来轻松恢复原始回文. >
rks解决方案的一句话，该解决方案不起作用，因为对于字符串S = 1121，它将创建字符串11211121，回文的长度大于或等于S的长度，但不是旋转的回文.如果我们更改解决方案以使其检查是否存在长度等于S长度的回文，它将起作用，但是我看不到任何直接解决方案如何更改以这种方式搜索最长子串的算法将搜索固定长度(len(S))的子字符串. (由于我是Stackoverflow的新手，并且没有足够的声誉，因此我没有在解决方案下写此评论)
第二句话-很抱歉没有包含Manacher的算法，如果有人链接到该算法的思想或某些实现，请在注释中添加它.
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!
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):
- sxs^Rp^Rp
- 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.
这篇关于验证字符串是否为旋转回文的有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
