高效验证字符串是否为旋转回文的方法？

Question

高效验证字符串是否为旋转回文的方法？

8

一个旋转回文就像是“1234321”，“3432112”。朴素的方法是将字符串切成不同的部分，再将它们连接起来，看看这个字符串是否是回文。由于有n个切割点，每个切割需要O(n) 的时间来检查字符串是否为回文，因此这种方法的时间复杂度是O(n^2)。我想知道是否有比这更好的解决方案。如果有的话，请给予建议。谢谢！

- Wei

问题：一个数字是否是回文数？这个数字123217898是否是旋转回文数？（换句话说，它能否被切成两个以上的子字符串） - saul672

1

123217898 不是一个旋转回文。 - DarthVader

5个回答

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")

- Ajinkya Vadane

2

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

对于您的示例，您将在“34321123432112”中进行研究，找到“21123432112”，它比您的初始字符串更长，因此是旋转回文。

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

编辑2：应该注意到，找到给定大小的回文并不容易。阅读Richard Stefanec发表的帖子下面的讨论以获取更多信息。

- rks

这里的O表示什么？你如何在 34321123432112 中搜索回文？ - DarthVader

与查找给定字符串的最长回文子串相同。这可以在线性时间内完成，参见：http://en.wikipedia.org/wiki/Longest_palindromic_substring - rks

0

我想提出一个简单的解决方案，只使用传统算法。它不能解决任何更难的问题，但对于您的任务应该足够了。它与其他两个提出的解决方案有些相似，但没有一个看起来足够简洁，让我仔细阅读。

第一步：将字符串连接到自身（abvc -> abvcabvc），如所有其他提出的解决方案。

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

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

结论：如果第三步找到了任何回文 - 那么该字符串是旋转回文。如果没有 - 那么它不是。

附言：Rabin Karp使用哈希，即使对于不重合的字符串也可能发生碰撞。因此，如果哈希检查引起等式，则进行验证暴力检查是一个好主意。尽管如此，如果在Rabin Karp中使用的哈希函数很好，解决方案的平摊速度应该保持O(n)。

- Boris Strandjev

-1

你可以将相同的模式添加到原始模式的末尾。例如，模式是1234321，则可以将相同的模式添加到末尾12343211234321。完成此操作后，您可以使用KMP或其他子字符串匹配算法来查找所需的字符串。如果匹配，则返回true。

- xy dai

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Richard Stefanec · Accepted Answer

根据维基百科的文章，可以在O(n)的时间内计算与长度为n的字符串S相同大小的数组A，使得：

当且仅当长度为i的S前缀是回文时，A[i]==1。

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

算法可以在以下文献中找到：

Manacher, Glenn (1975), "A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string"

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

每个（非旋转的）回文串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算法的思路或实现，如果有人有相关链接，请在评论中包含。