在花了大约6到8个小时尝试消化Manacher的算法后，我准备投入工作。但是在我这样做之前，这是黑暗中的最后一枪：有人能解释吗？我不在乎代码。我希望有人来解释该 算法 。
这似乎是其他人似乎喜欢解释该算法的地方：http : //www.leetcode.com/2011/11/longest- palindromic-substring-part-ii.html
我知道您为什么要将字符串转换为“ abba”到＃a＃b＃b＃a＃，然后我迷路了。例如，前面提到的网站的作者说，算法的关键部分是：
if P[ i' ] ≤ R – i, then P[ i ] ← P[ i' ] else P[ i ] ≥ P[ i' ]. (Which we have to expand past the right edge (R) to find P[ i ])
这似乎是错误的，因为他/她曾说过，当P [i’] = 7且P [i]不小于或等于R-i时，P [i]等于5。
如果您不熟悉该算法，请参见以下更多链接：http : //tristan-interview.blogspot.com/2011/11/longest-palindrome-substring- manachers.html（我已经尝试过此方法，但是术语令人恐惧和混乱。首先，未定义某些内容。此外，变量太多。您需要一个清单来回忆一下什么变量指的是什么。）
另一个是：http : //www.akalin.cx/longest-palindrome-linear-time（祝您好运）
该算法的基本要点是找到线性时间内最长的回文。可以在O（n ^ 2）中完成最小到中等的工作量。该算法被认为是相当“聪明”的，可以降低到O（n）。
我同意在链接说明中逻辑不正确。我在下面提供一些细节。
Manacher的算法填写表P [i]，其中包含以i为中心的回文延伸了多远。如果P [5] = 3，则位置5两侧的三个字符是回文的一部分。该算法利用了以下事实：如果您发现了一个长回文，您可以通过查看左侧的P值来快速填充回文右侧的P值，因为它们大部分应该是相同。
我将首先解释您所讨论的情况，然后根据需要扩展此答案。
R表示回文右侧以C为中心的索引。这是您指示的位置的状态：
C=11 R=20 i=15 i'=7 P[i']=7 R-i=5
逻辑是这样的：
if P[i']<=R-i: // not true else: // P[i] is at least 5, but may be greater
链接中的伪代码表明，如果测试失败，则P [i]应大于或等于P [i’]，但我认为它应大于或等于Ri，并对此进行了支持。
由于P [i’]大于Ri，所以以i’为中心的回文延伸到以C为中心的回文。我们知道以i为中心的回文至少要有Ri个字符宽，因为到目前为止，我们仍然具有对称性，但我们还必须进行明确搜索。
如果P [i’]不大于Ri，则以i’为中心的最大回文在以C为中心的最大回文中，因此我们知道P [i]不能大于P [i] ‘]。如果是这样，我们就会有矛盾。这意味着我们可以将以i为中心的回文扩展到P [i’]之外，但是如果可以的话，由于对称性，我们也可以将以i为中心的回文扩展出来，但是它已经应该尽可能大。
前面已经说明了这种情况：
C=11 R=20 i=13 i'=9 P[i']=1 R-i=7
在这种情况下，P [i’] <= Ri。由于距以C为中心的回文边缘还相距7个字符，因此我们知道i周围至少有7个字符与i’周围的7个字符相同。由于i’周围只有一个字符的回文，因此i周围也只有一个字符的回文。
j_random_hacker注意到逻辑应该更像这样：
if P[i']<R-i then P[i]=P[i'] else if P[i']>R-i then P[i]=R-i else P[i]=R-i + expansion
如果P [i’] <Ri，则我们知道P [i] == P [i’]，因为我们仍位于以C为中心的回文内部。
如果P [i’]> Ri，则我们知道P [i] == Ri，因为否则，以C为中心的回文将延伸到R之外。
因此，扩展实际上仅在P [i’] == Ri的特殊情况下才需要，因此我们不知道P [i]的回文是否可能更长。
通过设置P [i] = min（P [i’]，Ri），然后始终进行扩展，可以在实际代码中进行处理。这种方式不会增加时间复杂度，因为如果不需要扩展，则扩展所需的时间是恒定的。
