根据这篇维基百科文章，每个长度为 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）：
- sxs^Rp^Rp
- 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 的算法，如果有人有该算法的想法或某些实现的链接，请在评论中包含它。
