马纳彻算法——线性时间最长回文子串—

在里面马纳彻算法——第1部分，我们学习了一些基础知识和LPS长度数组。在这里，我们将看到如何有效地计算LPS长度数组。

null

为了有效地计算LPS数组，我们需要了解任何位置的LPS长度如何与之前计算的任何位置的LPS长度值相关。对于字符串“abaaba”，我们看到以下内容：

如果我们看看位置3：

位置2和位置4的LPS长度值相同
位置1和位置5的LPS长度值相同

我们从位置0开始从左到右计算LPS长度值，因此我们可以看到，如果我们已经知道位置1、2和3处的LPS长度值，那么我们可能不需要计算位置4和5处的LPS长度，因为它们等于位置3左侧相应位置处的LPS长度值。

如果我们看看位置6：

位置5和位置7的LPS长度值相同
位置4和位置8的LPS长度值相同

…………. 等等如果我们已经知道位置1、2、3、4、5和6的LPS长度值，那么我们可能不需要计算位置7、8、9、10和11的LPS长度，因为它们等于位置6左侧相应位置的LPS长度值。对于字符串“abababa”，我们可以看到以下内容：

如果我们已经知道位置1、2、3、4、5、6和7处的LPS长度值，那么我们可能不需要计算位置8、9、10、11、12和13处的LPS长度，因为它们等于位置7左侧相应位置处的LPS长度值。

你能理解为什么LPS长度值在字符串“abaaba”中的位置3、6、9周围是对称的吗？这是因为在这些位置周围有一个回文子串。位置7附近的字符串“abababa”也是如此。回文中心位置周围的LPS长度值总是对称（相同）的，这是真的吗？答案是否定的。查看字符串“abababa”中的位置3和11。两个位置的LPS长度均为3。直接的左右位置是对称的（值为0），但下一个位置不是对称的。位置1和5（位置3周围）不对称。同样，位置9和13（位置11周围）也不是对称的。

此时，我们可以看到，如果在以某个位置为中心的字符串中存在回文，那么围绕中心位置的LPS长度值可能是对称的，也可能不是对称的，这取决于某些情况。如果我们能够确定左右位置围绕中心位置对称的情况，我们不需要计算右位置的LPS长度，因为它将与已知的左侧对应位置的LPS值完全相同。我们在少数位置避免LPS长度计算，这使得马纳彻的算法是线性的。

在左右位置不围绕中心位置对称的情况下，我们比较左右两侧的字符以找到回文，但这里的算法也试图避免某些不比较。我们很快就会看到所有这些场景。

让我们介绍几个术语来进一步讨论：

中心位置 –这是计算LPS长度的位置，假设中心位置的LPS长度为d（即L[中心位置]=d）
中右位置 –该位置正好位于中心位置，d位置远离中心位置（即。 centerRightPosition=centerPosition+d )
中左位置 –这是离开中心位置和远离中心位置的d位置（即。 centerLeftPosition=中心位置–d )
当前正确位置 –这是中心位置右侧的位置，LPS长度尚未确定，必须计算
当前左位置 –这是中心位置左侧的位置，与当前右侧位置相对应 centerPosition–currentLeftPosition=currentRightPosition–centerPosition currentLeftPosition=2*中心位置–currentRightPosition
左回文 –回文i位于centerPosition左侧，即currentLeftPosition
右回文 –回文i位于centerPosition的右侧，即currentRightPosition
中心回文 –中心位置的回文

当我们处于已知LPS长度的中心位置时，我们也知道所有小于中心位置的位置的LPS长度。假设中心位置的LPS长度为d，即。 L[中心位置]=d

这意味着位置“centerPosition-d”到“centerPosition+d”之间的子串是回文。现在我们进一步计算大于中心位置的位置的长度。假设我们在currentRightPosition（>centerPosition），我们需要找到LPS长度。为此，我们看一下currentLeftPosition的LPS长度，它已经被计算出来了。

如果currentLeftPosition的LPS长度小于“centerRightPosition–currentRightPosition”，则currentRightPosition的LPS长度将等于currentLeftPosition的LPS长度。所以如果L[currentLeftPosition] 案例1 .

让我们考虑下面的字符串“abababa”场景：

                          (click to see it clearly)

我们计算了LPS长度到位置7，其中L〔7〕＝7，如果我们考虑位置7为中心位置，则中心左位置为0，中心位置为14。现在我们需要计算中心位置右侧其他位置的LPS长度。

对于currentRightPosition=8，currentLeftPosition为6，而L[currentLeftPosition]=0 此外，centerRightPosition–currentRightPosition=14–8=6 案例1适用于此处，因此L[currentRightPosition]=L[8]=0 案例1适用于位置10和12，因此， L[10]=L[4]=0 L[12]=L[2]=0

如果我们看位置9，那么： currentRightPosition=9 currentLeftPosition=2*centerPosition–currentRightPosition=2*7–9=5 centerRightPosition–currentRightPosition=14–9=5

这里的L[currentLeftPosition]=centerRightPosition–currentRightPosition，所以情况1不适用于这里。还要注意的是，centerRightPosition是字符串的最末端位置。这意味着中心回文是输入字符串的后缀。在这种情况下，L[currentRightPosition]=L[currentLeftPosition]。这是 案例2 .

案例2适用于位置9、11、13和14，因此： L[9]=L[5]=5 L[11]=L[3]=3 L[13]=L[1]=1 L[14]=L[0]=0

案例1和案例2到底发生了什么？这只是利用回文对称性，在没有任何字符匹配的情况下，寻找新位置的长度。

当一个较大长度的回文包含一个较小长度的回文，该回文以其自身中心的左侧为中心，那么根据对称性，将有另一个相同的较小回文以较大回文中心的右侧为中心。如果左侧较小回文不是较大回文的前缀，则 案例1 如果它是一个前缀，而较大的回文是输入字符串本身的后缀，则 案例2 应用。

如果左一回文完全包含在当前中心（中心回文）周围的最长回文中，且左一回文不是中心回文的前缀，则我放置在当前中心右侧的最长回文（右一回文）与我放置在当前中心左侧的最长回文（左一回文）一样长( 案例1 )或者（即，当i-left回文是中心回文的前缀时），如果中心回文是整个字符串的后缀( 案例2 ).

在案例1和案例2中，i-右回文不能比对应的i-左回文扩展得更多（你能想象为什么它不能扩展得更多吗？），所以右回文的LPS长度和左回文的LPS长度完全相同。

这里，i-left和i-right回文都完全包含在中间回文中（即L[currentLeftPosition]<=centerRightPosition–currentRightPosition）现在，如果i-left回文不是中间回文的前缀（L[currentLeftPosition]

如果我们用centerPosition=11查看以下内容，那么

                          (click to see it clearly)

centerLeftPosition为11–9=2，centerRightPosition为11+9=20 如果我们取currentRightPosition=15，那么currentLeftPosition就是7。案例1适用于这里，因此L[15]=3。位置7的左回文是“bab”，它完全包含在位置11的中间回文中（即“dbabcbad”）。我们可以看到，i-right回文（在位置15）不能比i-left回文（在位置7）扩展得更多。

如果有扩展的可能性，我左边的回文可能已经扩展得更多了。但不存在这样的可能性，因为左回文是中间回文的前缀。所以，由于对称性，i-右回文和i-左回文完全相同，不能再扩展了。这使得情况1中的L[currentRightPosition]=L[currentLeftPosition]。

现在，如果考虑中心位置＝19，则中心左位置＝12和中心右位＝26。如果我们取currentRightPosition=23，则currentLeftPosition为15。案例2适用于这里，因此L[23]=3。位置15的左回文是“bab”，它完全包含在位置19的中间回文中（即“babdbab”）。在第二种情况下，i-left回文是中间回文的前缀，i-right回文不能扩展超过i-left回文的长度，因为中间回文是输入字符串的后缀，所以没有更多的字符可以比较和扩展。在案例2中，这使得L[currentRightPosition]=L[currentLeftPosition]。

案例1： L[currentRightPosition]=L[currentLeftPosition]适用于以下情况：

左回文完全包含在中间回文中
左回文不是中间回文的前缀

当 L[currentLeftPosition]

案例2： L[currentRightPosition]=L[currentLeftPosition]适用于以下情况：

左回文是中间回文的前缀（也意味着完全包含）
中间回文是输入字符串的后缀

当 L[currentLeftPosition]=中心右侧位置–当前右侧位置（用于1 ^圣条件）和 centerRightPosition=2*N，其中N是输入字符串长度N（对于2 ^钕条件）。

案例3： L[currentRightPosition]>=L[currentLeftPosition]适用于以下情况：

左回文是中心回文的前缀（所以左回文完全包含在中心回文中）
中心回文不是输入字符串的后缀

当 L[currentLeftPosition]=中心右侧位置–当前右侧位置（用于1 ^圣条件）和 centerRightPosition<2*N，其中N是输入字符串长度N（对于2 ^钕条件）。在这种情况下，存在i-右回文扩展的可能性，因此i-右回文的长度至少与i-左回文的长度相同。

案例4： L[currentRightPosition]>=centerRightPosition–currentRightPosition适用于以下情况：

左回文不完全包含在中间回文中

当 L[currentLeftPosition]>centerRightPosition–currentRightPosition 在这种情况下，i-right回文的长度至少与（centerRightPosition–currentRightPosition）一样长，并且存在i-right回文扩展的可能性。

在下图中，

                          (click to see it clearly)

如果我们取中间位置7，那么情况3适用于currentRightPosition 11，因为currentLeftPosition 3处的i-left回文是中间回文的前缀，而i-right回文不是输入字符串的后缀，所以这里的L[11]=9大于i-left回文长度L[3]=3。在这种情况下，可以保证L[11]至少为3，因此在实现中，我们为1 ^圣设置L[11]=3，然后我们尝试通过比较从距离4开始的左右两侧的字符来扩展它（到距离3为止，已经知道字符将匹配）。

如果我们选择中间位置11，那么案例4适用于currentRightPosition 15，因为L[currentLeftPosition]=L[7]=7>centerRightPosition–currentRightPosition=20–15=5。在这种情况下，可以保证L[15]至少为5，因此在实现中，我们为1 ^圣设置L[15]=5，然后我们尝试通过比较从距离5开始的左右两侧的字符来扩展它（到距离5为止，已经知道字符将匹配）。

现在剩下一点要讨论的是，当我们在一个中心位置工作，计算不同右位置的LPS长度时，如何知道下一个中心位置是什么。如果以currentRightPosition为中心的回文扩展到centerRightPosition之外，我们将centerPosition更改为currentRightPosition。

在这里，我们看到了四种不同的情况，即一个职位的LPS长度如何取决于前一个职位的LPS长度。在里面第三部分，我们讨论了它的代码实现，我们也以不同的方式研究了这四种情况，并实现了这一点。

本文由导演。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章

马纳彻算法——线性时间最长回文子串——第2部分