8

旋转回文就像“1234321”、“3432112”。朴素的方法会将字符串切割成不同的片段并将它们连接回来，看看字符串是否是回文。这将需要 O(n^2)，因为有 n 个切割，并且对于每个切割，我们需要 O(n) 来检查字符串是否是回文。我想知道是否有比这更好的解决方案。估计是这样，求指教。

谢谢！

4

5 回答 5

6

根据this wikipedia article，对于每个长度为n的字符串S，在时间O(n)中计算一个相同大小的数组A是可能的，这样：

A[i]==1 如果 S 的长度为 i 的前缀是回文。

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

该算法应该可以在以下位置找到：

Manacher, Glenn (1975)，“一种新的线性时间“在线”算法，用于查找字符串的最小初始回文数”

换句话说，我们可以在线性时间内检查字符串的哪些前缀是回文。我们将使用这个结果来解决提出的问题。

每个（非旋转）回文 S 具有以下形式 S = psxs^Rp^R。

其中“x”是回文的中心（空字符串或一个字母字符串），“p”和“s”是（可能为空）字符串，“s^R”表示“s”字符串反转。

从这个字符串创建的每个旋转回文都具有以下两种形式之一（对于某些 p）：

  1. sxs^Rp^Rp
  2. p^Rpsxs^R

这是真的，因为您可以选择是否在回文中间之前或之后剪切一些子字符串，然后将其粘贴到另一端。

可以看到，子串“p^Rp”和“sxs^R”都是回文，其中一个是偶数长度，另一个是奇数长度，当且仅当 S 是奇数长度。

我们可以使用维基百科链接中提到的算法来创建两个数组 A 和 B。数组 A 是通过检查哪些前缀是回文而 B 是后缀来创建的。然后我们搜索一个值 i 使得 A[i]==B[i]==1 使得前缀或后缀具有偶数长度。如果提议的字符串是旋转回文并且偶数部分是“p^Rp”子字符串，我们将找到这样的索引，因此我们可以通过将该字符串的一半移动到字符串的另一端来轻松恢复原始回文。

rks 对解决方案的一个评论是，该解决方案不起作用，因为对于字符串 S = 1121，它将创建字符串 11211121，其回文长度大于或等于 S 的长度，但它不是旋转回文。如果我们更改解决方案以检查是否存在长度等于 S 长度的回文，它会起作用，但我没有看到任何直接的解决方案如何更改搜索最长子字符串的算法，使其将搜索固定长度的子字符串 (len(S))。（我没有在解决方案下写这个作为评论，因为我是 Stackoverflow 的新手并且没有足够的声誉这样做）

第二条评论 - 很抱歉没有包含 Manacher 的算法，如果有人链接到算法的想法或某些实现，请将其包含在评论中。

于 2012-09-05T18:28:16.210 回答
2

将字符串连接到自身，然后在新字符串中进行经典回文研究。如果你找到一个长度大于或等于原始字符串长度的回文，你就知道你的字符串是一个旋转的回文。

对于您的示例，您将在34321123432112, find中进行研究21123432112，该字符串比您的初始字符串长，因此它是一个旋转回文。

编辑：正如 Richard Stefanec 所指出的，我的算法在 上失败1121，他建议我们>=将长度上的测试更改为=。

EDIT2：应该注意的是，找到给定大小的回文显然并不容易。阅读 Richard Stefanec 帖子下的讨论以获取更多信息。

于 2012-09-05T16:56:56.823 回答
2 
#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")
于 2019-03-20T20:34:51.867 回答
0

我想提出一个简单的解决方案，只使用传统算法。它不会解决任何更难的问题，但它应该足以完成您的任务。它与其他两个提议的解决方案有些相似，但它们似乎都不够简洁，我可以仔细阅读。

第一步：将字符串连接到自身（abvc- > abvcabvc），就像在所有其他建议的解决方案中一样。

第二步：对新获得的字符串及其反转进行Rabin-Karp 预计算（使用滚动哈希）。

第三步：让字符串为 length n。对于每个索引i，0...n-1检查双倍字符串的子字符串[i, i + n - 1]是否在恒定时间内是回文，使用 Rabin-Karp 预计算（基本上，在正向和反向方向的子串中获得的值应该相等）。

结论：如果第三步发现任何回文 - 那么字符串是旋转回文。如果不是 - 那么它不是。

PS：Rabin Karp 使用哈希，即使是不重合的字符串也可能发生冲突。因此，如果哈希检查引起了相等性的验证暴力检查，这是一个好主意。尽管如此，如果 Rabin Karp 中使用的散列函数是好的，那么解决方案的摊销速度应该保持不变O(n)。

于 2012-09-06T10:36:26.980 回答
-1

您可以将相同的图案添加到原始图案的末尾。比如pattern是1234321，那么你可以在12343211234321的末尾添加相同的pattern。完成后，你可以使用KMP或其他子串匹配算法来找到你想要的字符串。如果匹配，则返回 ture。

于 2015-01-03T12:26:42.090 回答