Manacher算法 线性时间找到最大子回文字符串

Manacher算法翻译自 geeksforgeeks文章
我们在set1和set2中分别讨论了暴力O($n^3$n3)解法和优化的O($n^2$n2)解法，set2中寻找回文字符串的方法是从字符串中心开始往两端逐一比较字符，如果两边的字符匹配，则他们是回文。
我们先考虑一下“abababa”。
这个字符串的中心是第四个字符b(index=3)。
然而中心不只是字符，也可能是两个字符之间的位置。
考虑偶数长度的字符串“abaaba” ，这个字符串的中心是第三个字符a和第四个字字符a之间的位置。
个
为了找到最长回文子字符串，一种方法是找到可能的2N+1个中心(N个字符位置和N-1个字符之间的位置，以及两个最左最右两边的位置)，在这2N+1个中心，往左右做字符匹配，从而找到最长子字符串的前缀和后缀(longest prefix suffix，LPS)。这种O($n^2$n2)思路在set2中已经讨论过了，
我们来考虑下图的 “abababa” 和 “abaaba”

在这两个字符串中，中心位置(第一个字符串的位置7和第二个字符串的位置6)的两边是对称的，如果我们想计算以2N+1个位置为中心的最大回文子字符串，回文的对称性可以帮助我们避免一些重复计算，例如，如果有一个以位置P为中心，长度为L的回文字符串，对于下一个位置P+1，我们就不需要比较P+1左右边的所有字符，因为我们已经知道了位置P之前的LPS信息。这种对之前信息的使用使得Manacher算法是线性时间的。
在上图的字符串 “abababa”中，有15个中心位置，我们需要计算每个位置的最大回文子字符串。
位置0：没有LPS(左边没有字符来比较)
位置1：LPS是‘a’，因此LPS长度为1
位置2：没有LPS(左边字符a和右边字符b不匹配)
…
我们将这些回文字符串的长度存储在一个数组L中，它和字符串的关系如下图：


在LPS数组L中：
在奇数位置(字符位置)的LPS长度是奇数并且大于等于1(当两边没有任何字符串匹配时，长度为1)
在偶数位置(两字符之间的位置,也包括最左最右边)的LPS长度是偶数并且大于等于0。

这里需要注意位置的概念和下标的概念。对于一个长度为N的字符串S，下标范围是0到N-1，位置从0到2N(总共2N+1个位置)。

LPS长度可以从位置和下标两方面理解，在位置处的LPS(L[i]=d)意味着：
1：从位置i-d到位置i+d的回文字符串的长度是d
2：从下标$\frac{i-d}{2}$2i−d​到$\frac{i+d}{2}-1$2i+d​−1的回文字符串长度是d
举个例子，字符串 “abaaba”, L[3] = 3，意味着从位置0(3-3)到位置6(3+3)是一个长度为3的回文aba；也意味着从下标 0 [(3-3)/2] 到 2 [(3+3)/2 – 1]是回文aba。

所以现在的任务就是高效的计算LPS数组，因为得到该数组之后，就能得到字符串S的最大回文子字符串。
我们首先要明白LPS的长度和之前已经计算过的位置的LPS长度的关系。
对字符串“abaaba”：

对于位置3：
LPS长度在位置2和4都是0
LPS长度在位置1和5都是1
我们从位置0开始从左往右计算LPS长度，因此，如果我们知道了位置1，2，3上的LPS长度，我们就不需要计算位置4和5的LPS长度因为他们等于位置3左边的LPS长度。

对于位置6：
LPS长度在位置5和7相同
LPS长度在位置4和8相同
因此如果我们知道了位置1,2,3,4,5,6的LPS长度，我们就不需要计算位置7,8,9,10,11的LPS长度

我们再看字符串“abababa”

如果我们知道位置1到7de LPS长度，就不需要计算8到13的，因为他们的LPS长度关于位置7对称。
你能发现为什么在字符串“abaaba"中位置3，6，9两边的LPS长度对称吗？这是因为这些位置周围都是回文字符串。
那是不是只要在回文字符串中心的两侧，LPS长度都相同呢？
答案是 否。
在字符串”abababa"的位置3和11，他们的的LPS长度都是3，往左和往右一步是对称的，但是两步就不对称了，也就是说，位置1和5的LPS长度并不相同，位置9和13的LPS长度也不相同。
根据之前的研究，某些中心位置周围的LPS长度可能会也可能不会对称，如果我们能够发现什么情况下中心左右位置的LPS长度是对称的，我们就只需要计算一边的LPS长度(只用计算左边，不用算右边)
在中心左右位置的LPS长度不对称的时候，我们需要比较中心左边和右边的字符来找到回文字符串，但是也有算法让我们可以避免这些比较运算。

在介绍这些算法之前，先介绍几个概念：
1 centerPosition：这是LPS长度的中心位置，意味着中心位置的LPS长度是d

2 centerRightPosition：这是中心位置右边d个位置的地方(centerRightPosition = centerPosition + d)，其中d是中心位置的LPS长度

3 centerLeftPosition：这是中心位置左边d个位置的地方(centerLeftPosition = centerPosition - d)

4 currentRightPosition：这是中心位置的右边并且其LPS长度未知的位置(需要被计算)

5 currentLeftPosition：这是中心位置左边，和currentRightPosition对称的位置(centerPosition – currentLeftPosition = currentRightPosition – centerPosition)

6 i-left palindrome：以中心左边第i个位置(currentLeftPosition)为中心的回文字符串
7 i-right palindrome：以中心右边第i个位置(currentRightPosition)为中心的回文字符串
8 center palindrome： 中心位置的回文字符串
当我们在LPS长度已知的中心位置，同时我们也知道中心位置左边所有位置的LPS长度，
假设L[centerPosition] = d
这意味着位置 “centerPosition-d” 到 “centerPosition+d”是一个回文字符串。
现在我们要计算中心位置右边位置的LPS长度，假设我们现在在urrentRightPosition ( > centerPosition)，需要计算这个位置的LPS长度，
我先看已经计算过的 currentLeftPosition的LPS长度
如果currentLeftPosition的LPS长度比“centerRightPosition-currentRightPosition”的值小，那么currentRightPosition的LPS长度将会和currentLeftPosition的LPS长度相同，即：
L[currentRightPosition] = L[currentLeftPosition] if L[currentLeftPosition] < centerRightPosition – currentRightPosition.
上述是case1
我们结合下图中的“abababa”看看case1，我们已经计算出了位置0到7的LPS长度，一直L[7]=7，将位置7作为centerPosition，那么centerLeftPosition 是位置0 ， centerRightPosition是位置 14.
我们现在需要计算centerPosition右边位置的LPS长度。
对currentRightPosition = 8, currentLeftPosition= 6
L[currentLeftPosition] = 0
此时满足L[currentLeftPosition] < centerRightPosition – currentRightPosition
因此 L[8] =L[6]= 0
同理
L[4]=0<14-10，所以L[10]=L[4]=0
L[2]=0<14-12，所以L[12] = L[2] = 0

如果我们观察上图中位置9，假设 currentRightPosition = 9
currentLeftPosition = 2* centerPosition – currentRightPosition = 2*7 – 9 = 5
centerRightPosition – currentRightPosition = 14 – 9 = 5
这里 L[currentLeftPosition]=5 = centerRightPosition – currentRightPosition，所以case1不适用了，
That means center palindrome is suffix of input string. In that case, L[currentRightPosition] = L[currentLeftPosition]. This is Case 2.

Case 2 applies to positions 9, 11, 13 and 14, so:
L[9] = L[5] = 5
L[11] = L[3] = 3
L[13] = L[1] = 1
L[14] = L[0] = 0

case1和case2中发生了什么？
What is really happening in Case 1 and Case 2? This is just utilizing the palindromic symmetric property and without any character match, it is finding LPS length of new positions.

When a bigger length palindrome contains a smaller length palindrome centered at left side of it’s own center, then based on symmetric property, there will be another same smaller palindrome centered on the right of bigger palindrome center. If left side smaller palindrome is not prefix of bigger palindrome, then Case 1 applies and if it is a prefix AND bigger palindrome is suffix of the input string itself, then Case 2 applies.

如果 i-left palindrome完全包含在中心回文字符串中并且 i-left palindrome 不是中心回文字符串的前缀(prefix),这是case1，那么 currentCenter右边i个位置的最长回文字符串(i-right palindrome)是和currentCenter左边第i个位置的最长回文字符串( i-left palindrome) 一样长的。
如果i-left palindrome是中心回文字符串的前缀

mmp 这个前缀后缀什么意思，，，我搞懂了再继续翻译。。。。
The longest palindrome i places to the right of the current center (the ) is as long as the longest palindrome i places to the left of the current center (the i-left palindrome)
if the i-left palindrome is completely contained in the longest palindrome around the current center (the center palindrome) and the i-left palindrome is not a prefix of the center palindrome (Case 1) or (i.e. when i-left palindrome is a prefix of center palindrome) if the center palindrome is a suffix of the entire string (Case 2).

In Case 1 and Case 2, i-right palindrome can’t expand more than corresponding i-left palindrome (can you visualize why it can’t expand more?), and so LPS length of i-right palindrome is exactly same as LPS length of i-left palindrome.

Here both i-left and i-right palindromes are completely contained in center palindrome (i.e. L[currentLeftPosition] <= centerRightPosition – currentRightPosition)
Now if i-left palindrome is not a prefix of center palindrome (L[currentLeftPosition] < centerRightPosition – currentRightPosition), that means that i-left palindrome was not able to expand up-to position centerLeftPosition.