Wei*_*Wei 8 algorithm palindrome
旋转的回文类似于"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的算法,如果有人链接到算法的想法或某些实现,请在评论中包含它.
将字符串连接到自身，然后在新字符串中进行经典的回文研究。如果你发现一个回文串的长度大于或等于原始字符串的长度，你就知道你的字符串是一个旋转回文串。
\n\n对于您的示例，您将在 中进行研究34321123432112，发现21123432112，它比您的初始字符串长，因此它是一个旋转回文。
编辑：\xc2\xa0as Richard Stefanec 指出，我的算法在 上失败1121，他建议我们将>=长度测试更改为=。
EDIT2：应该指出的是，找到给定大小的回文显然并不容易。请阅读 Richard Stefanec 帖子下的讨论以获取更多信息。
\n