旋转的回文类似于“1234321”，“3432112”。天真的方法将把字符串切成不同的部分并将它们连接起来，看看字符串是否是回文。这将花费O（n ^ 2），因为有n个切割，并且对于每个切割，我们需要O（n）来检查该串是否是回文。我想知道是否有比这更好的解决方案。我想是的，请指教。
谢谢！
根据这个维基百科文章，有时长度为n的每个字符串S在时间O（n）中计算出相同大小的数组A，这样：
A [i] == 1 iff长度为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）：
这是真的，因为您可以选择是在回文中间之前还是之后切割一些子串，然后将其粘贴到另一端。
可以看出，子串“p ^ Rp”和“sxs ^ R”都是回文，其中一个是偶数长度而另一个是奇数长度iff S是奇数长度。
我们可以使用维基百科链接中提到的算法来创建两个数组A和B.数组A是通过检查哪些前缀是回文，B是后缀来创建的。然后我们搜索值i，使得A [i] == B [i] == 1，使得前缀或后缀具有偶数长度。如果建议的字符串是旋转回文并且偶数部分是“p ^ Rp”子字符串，我们将找到这样的索引，因此我们可以通过将该字符串的一半移动到字符串的另一端来容易地恢复原始回文。
对rks解决方案的一个评论，这个解决方案不起作用，因为对于字符串S = 1121，它将创建字符串11211121，其长度大于或等于S的长度，但它不是旋转的回文。如果我们更改解决方案，以便检查是否存在长度等于S的长度的回文，它会工作，但我没有看到任何直接的解决方案如何更改搜索最长子串的算法，以便它将搜索固定长度的子串（len（S））。 （我没有把它写成解决方案下的评论，因为我是Stackoverflow的新手并没有足够的声誉这样做）
第二句 - 我很抱歉不包括Manacher的算法，如果有人链接到算法的想法或某些实现，请在评论中包含它。
将字符串连接到自身，然后在新字符串中进行经典的回文研究。如果您发现长度大于或等于原始字符串长度的回文，则您知道您的字符串是旋转的回文结构。
对于你的例子，你会在34321123432112进行研究，找到比你的初始字符串长的21123432112，所以它是一个旋转的回文。
编辑：正如Richard Stefanec所说，我的算法在1121失败，他建议我们改变>=长度的=测试。
EDIT2：应该注意的是，找到给定大小的回文并不容易。阅读Richard Stefanec帖子下的讨论，了解更多信息。
#Given a string, check if it is a rotation of a palindrome.
#For example your function should return true for “aab” as it is a rotation of “aba”.
string1 = input("Enter the first string")
def check_palindrome(string1):
#string1_list = [word1 for word1 in string1]
#print(string1_list)
string1_rotated = string1[1::1] + string1[0]
print(string1_rotated)
string1_rotated_palindrome = string1_rotated[-1::-1]
print(string1_rotated_palindrome)
if string1_rotated == string1_rotated_palindrome:
return True
else:
return False
isPalindrome = check_palindrome(string1)
if(isPalindrome):
print("Rotated string is palindrome as well")
else:
print("Rotated string is not palindrome")
我想提出一个简单的解决方案，仅使用传统算法。它不会解决任何更难的问题，但它应该足以完成您的任务。它有点类似于其他两个提议的解决方案，但它们似乎都不够简洁，我可以仔细阅读。
第一步：将字符串连接到自身（abvc - > abvcabvc），就像在所有其他提议的解决方案中一样。
第二步：对新获得的字符串执行Rabin-Karp precalculation（使用滚动哈希）并将其反转。
第三步：让字符串长度为n。对于每个索引iin 0...n-1使用Rabin-Karp预先计算检查双重字符串[i, i + n - 1]的子串是否是恒定时间的回文（基本上获得的前向和反向子串中的值应相等）。
结论：如果第三步发现任何回文 - 那么绳子旋转回落。如果不是 - 那就不是。
PS：Rabin Karp使用哈希，即使对于不重合的弦也可能发生碰撞。因此，如果由哈希检查引起，则对验证暴力检查是否相等是个好主意。仍然如果Rabin Karp中使用的哈希函数是好的，解决方案的摊销速度应保持为O(n)。
您可以将相同的模式添加到原始模式的末尾。例如，模式是1234321，然后您可以将相同的模式添加到末尾12343211234321.执行此操作后，您可以使用KMP或其他子字符串匹配算法来查找所需的字符串。如果匹配，返回ture。