algorithm - Manacher 算法(在线性时间内找到最长回文子串的算法)

Question

在尝试消化 Manacher 的算法大约 6-8 小时后，我准备认输。但在我这样做之前，这是黑暗中的最后一枪:谁能解释一下？我不关心代码。我希望有人解释一下算法。

这里似乎是其他人在解释算法时喜欢的地方: 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 (我试过这个，但术语很糟糕而且令人困惑。首先，有些东西没有定义。而且，变量太多。你需要一个 list 来记忆哪个变量指的是什么。)

另一个是:http://www.akalin.cx/longest-palindrome-linear-time (祝你好运)

该算法的基本要点是在线性时间内找到最长的回文。它可以在 O(n^2) 中以最小到中等的努力完成。该算法应该非常“聪明”，可以将其降低到 O(n)。

Answer 1

我同意链接的解释中的逻辑不太正确。我在下面给出了一些细节。

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']，但我认为它应该大于等于R-i，并且解释支持

因为 P[i'] 大于 R-i，以 i' 为中心的回文串延伸超过以 C 为中心的回文串。我们知道以 i 为中心的回文串至少有 R-i 个字符宽，因为我们仍然有对称性那个点，但我们必须在那个点之外明确地搜索。

如果 P[i'] 不大于 R-i，那么以 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']<=R-i。由于我们距离以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'] < R-i，那么我们知道 P[i]==P[i']，因为我们仍然在以 C 为中心的回文中。

如果 P[i'] > R-i，那么我们知道 P[i]==R-i，否则以 C 为中心的回文将延伸到 R 之后。

所以实际上只有在 P[i']==R-i 的特殊情况下才需要扩展，所以我们不知道 P[i] 处的回文是否可能更长。

这在实际代码中是通过设置 P[i]=min(P[i'],R-i) 然后一直扩展来处理的。这种做法不会增加时间复杂度，因为如果不需要展开，展开所花费的时间是常数。