Manacher算法（在线性时间内找到最长回文子串的算法）

Manacher算法（在线性时间内找到最长回文子串的算法）

我同意在链接说明中逻辑不正确。我在下面提供一些细节。

Manacher的算法填写表P [i]，其中包含以i为中心的回文延伸了多远。如果P [5] =
3，则位置5两侧的三个字符是回文的一部分。该算法利用了以下事实：如果您发现了一个长回文，您可以通过查看左侧的P值来快速填充回文右侧的P值，因为它们大部分应该是相同。

我将首先解释您所讨论的情况，然后根据需要扩展此答案。

R表示回文右侧以C为中心的索引。这是您指示的位置的状态：

C=11R=20i=15i'=7P[i']=7R-i=5

逻辑是这样的：

if P[i']<=R-i:  // not trueelse: // 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=11R=20i=13i'=9P[i']=1R-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-ielse 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），然后始终进行扩展，可以在实际代码中进行处理。这种方式不会增加时间复杂度，因为如果不需要扩展，则扩展所需的时间是恒定的。