Manacher的算法（算法来找到线性时间最长的回文子） [英] Manacher's algorithm (algorithm to find longest palindrome substring in linear time)

问题描述

花费约6-8小时试图消化Manacher的算法后，我准备认输。但在此之前我做的，这里是在黑暗中做最后一搏：任何人都可以解释一下吗？我不关心code。我希望有人来解释算法

After spending about 6-8 hours trying to digest the Manacher's algorithm, I am ready to throw in the towel. But before I do, here is one last shot in the dark: can anyone explain it? I don't care about the code. I want somebody to explain the ALGORITHM.

下面似乎是一个地方，其他人似乎很喜欢在解释算法： <一href="http://www.leet$c$c.com/2011/11/longest-palindromic-substring-part-ii.html">http://www.leet$c$c.com/2011/11/longest-palindromic-substring-part-ii.html

Here seems to be a place that others seemed to enjoy in explaining the algorithm: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

我明白你为什么会想改造字符串，比方说，利群，以＃A＃B＃B＃A＃ 较后，我迷路了。例如，pviously提到网站的$ P $的作者说，该算法的关键部分是：

I understand why you would want to transform the string, say, 'abba' to #a#b#b#a# After than I'm lost. For example, the author of the previously mentioned website says the key part of the algorithm is:

                      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]于等于5当P [I'] = 7和P [i]为不小于或等于R - 岛

This seems wrong, because he/she says at one point that P[i] equals 5 when P[i'] = 7 and P[i] is not less or equal to R - i.

如果您不熟悉的算法，这里有一些更多的链接：<一href="http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html">http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html （我试过这一个，但术语是可怕和混乱。首先，有些事情是没有定义的。而且，太多的变数，您需要一个清单召回是指什么什么的变量。）

If you are not familiar with the algorithm, here are some more links: http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (I've tried this one, but the terminology is awful and confusing. First, some things are not defined. Also, too many variables. You need a checklist to recall what variable is referring to what.)

另外一个是：<一href="http://www.akalin.cx/longest-palindrome-linear-time">http://www.akalin.cx/longest-palindrome-linear-time （好运气）

Another is: http://www.akalin.cx/longest-palindrome-linear-time (good luck)

该算法的基本要点是，找到最长回文线性时间。它可以在O进行（N ^ 2）配有一个最小的努力中量。该算法应该是相当聪明得到它下降到O（N）。

The basic gist of the algorithm is to find the longest palindrome in linear time. It can be done in O(n^2) with a minimum to medium amount of effort. This algorithm is supposed to be quite "clever" to get it down to O(n).

推荐答案

我认同的逻辑是不完全正确的链接的说明。我给下面的一些细节。

I agree that the logic isn't quite right in the explanation of the link. I give some details below.

Manacher算法填充在表P [I]含有多远回文集中在我延伸。如果P [5] = 3，则在位置5任一侧三个字符是回文的一部分。该算法利用这样的事实，如果你发现了一个长的回文，你可以在P的右侧回文的价值填补优势迅速通过看P的值在左侧，因为他们应该大多是一样的。

Manacher's algorithm fills in a table P[i] which contains how far the palindrome centered at i extends. If P[5]=3, then three characters on either side of position five are part of the palindrome. The algorithm takes advantage of the fact that if you've found a long palindrome, you can fill in values of P on the right side of the palindrome quickly by looking at the values of P on the left side, since they should mostly be the same.

我将解释你在谈论的情况下启动，然后根据需要，我会扩大这个答案。

I'll start by explaining the case you were talking about, and then I'll expand this answer as needed.

R表示右侧的C.集中在这里，回文结构的指标是国家在您指定的位置：

R indicates the index of the right side of the palindrome centered at C. Here is the state at the place you indicated:

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

的伪code中的链接指示P [i]于应大于或等于P [I']如果测试失败，但是相信它应大于或等于Ri和解释备份这件事。

The pseudo-code in the link indicates that P[i] should be greater than or equal to P[i'] if the test fails, but I believe it should be greater than or equal to R-i, and the explanation backs that up.

由于P [Ⅰ']大于日，中心在我的回文'延伸经过在C处居中我们知道该回文中心在我将在宽至少日字符，因为我们还有对称高达回文这一点，但我们必须明确地搜索不止于此。

Since P[i'] is greater than R-i, the palindrome centered at i' extends past the palindrome centered at C. We know the palindrome centered at i will be at least R-i characters wide, because we still have symmetry up to that point, but we have to search explicitly beyond that.

如果P [Ⅰ']一直不大于日，然后集中在我最大回文'是内居中位于C最大回文的，所以我们将知道，P [i]于不能任何大于P [Ⅰ']。如果是，我们将有一个矛盾。这将意味着我们将能够延长在我中心超出P [I']回文，但如果我们能，那么我们也将能够延长集中在我的回文由于对称性，但它已经是应该是尽可能的大。

If P[i'] had been no greater than R-i, then the largest palindrome centered at i' is within the largest palindrome centered at C, so we would have known that P[i] couldn't be any larger than P[i']. If it was, we would have a contradiction. It would mean that we would be able to extend the palindrome centered at i beyond P[i'], but if we could, then we would also be able to extend the palindrome centered at i' due to the symmetry, but it was already supposed to be as large as possible.

这个案件说明了previously：

This case is illustrated previously:

C=11
R=20
i=13
i'=9
P[i']=1
R-i=7

在这种情况下，P [Ⅰ']其中; = R-I。因为我们还在7个字符远离中心在C中的回文的边缘，我们知道，我身边至少有7个字符都是一样的7个字符我周围。因为，只有一个字符周围回文I'，有一个一个字符回文周围我以及

In this case, P[i']<=R-i. Since we are still 7 characters away from the edge of the palindrome centered at C, we know that at least 7 characters around i are the same as the 7 characters around i'. Since there was only a one character palindrome around i', there is a one character palindrome around i as well.

j_random_hacker注意到，逻辑应该是更喜欢这样的：

j_random_hacker noticed that the logic should be more like this:

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 [Ⅰ']其中;日，那么我们知道P [I] == P [I']，因为我们仍然集中在C中的回文中。

If P[i'] < R-i, then we know that P[i]==P[i'], since we're still inside the palindrome centered at C.

如果P [I']>日，那么我们知道P [I] ==日，否则集中在C中的回文会延续过去的R上。

If P[i'] > R-i, then we know that P[i]==R-i, because otherwise the palindrome centered at C would have extended past R.

所以，扩张确实是只需要在特殊情况下，P [I'] ==日，所以我们不知道，如果回文为P [I]可能会更长。

So the expansion is really only necessary in the special case where P[i']==R-i, so we don't know if the palindrome at P[i] may be longer.

这是在实际的code。通过设置P [I] = MIN（P [I']，日），然后一直在扩张处理。这样做不会增加了时间复杂度，因为如果没有扩张是必要的，所用的时间来做膨胀是恒定

This is handled in the actual code by setting P[i]=min(P[i'],R-i) and then always expanding. This way of doing it doesn't increase the time complexity, because if no expansion is necessary, the time taken to do the expansion is constant.

这篇关于Manacher的算法（算法来找到线性时间最长的回文子）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！