如何在最长回文子串算法中选择下一个中心？

Question

4

这是一个关于最长回文子串算法的问题，该算法曾在此处讨论过。引用的博客文章解释了该算法，其中提到：“为了选择下一个中心，取当前回文串最长回文后缀的中心”。不幸的是，他们没有提供证明，而我也不太理解为什么下一个中心是当前回文串最长回文后缀的中心。

有人能证明/解释吗？

- Michael

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fattie · Accepted Answer

我们现在要向右移动…

假设你的“当前”回文有40个字母（可能是以100号位置为中心的）。你想找一个更大的回文。

（好吧，可能会有一个900个字母长、距离这个回文右边50000个字母的更大的回文——完全与这个无关。没关系。但我们将来会提到它。现在，我们必须将中心移到右侧，同时寻找比40还要长的回文。有道理吗？）

所以我们必须向右移动——我们可以移动一步。但是我们希望尽可能地向右移动而不会漏掉任何一个。

现在，如果右侧的下一个回文要包括这个回文……实际上，它必须包括这组40个字母的最右边的字母。（它不能再往左了，因为我们已经检查过了，所以它必须位于100之后，并且因为它将比40更长，所以它必须包括我们右手边的字母，＃120。）

那么我们需要往回走多远呢？

嗯，你不能往回走（从120）比一个回文还要远！如果中间不是回文，它永远也不会成为回文。

3333333333333331110111

你只能“回到”0。例如，留在0左侧的1永远不能成为回文。

所以很简单。你必须包括我们最右边的字母（如果我们要包括任何人），而且你希望它尽可能大，它必须是回文，因为回文只能以回文为中心开始（我指的是“从中间”）。

在上面的例子中，左侧的1或0，或者说最右侧的3，在无论右侧有什么东西时都永远不能成为回文中心。它们周围没有回文，所以它们永远不能成为回文中心！

请注意，三个3中间的那个3可能会成为更大的回文中心……但别忘了，我们已经检查过这是到目前为止最长的回文（基于中心点，从左边算），所以这不可能是真的。

因此，任何比这个更长的回文——换句话说，下一个可能的比这个更长的回文的起点——就是0。

换句话说，它只是我们当前在右侧具有的最大回文字符串的中心。（因此，不是“111”这个短的回文字符串，而是“1110111”，它是您在右侧看到的最长回文字符串。）

实际上，我们需要检查的两种可能性是（A）倒数第二个位置的“0”和（B）“1”。当然，在这两种情况下，我们必须从左到右进行检查，因此（A）中的“0”确实是下一个要检查的。

不要忘记，这两个（问题中的0和1）等同于说“末尾有一个1110111的回文字符串，并且末尾有一个较短的111回文字符串”。

当然，1110111更长，因此1110111的中心显然在111的中心左侧。

卡住右侧的最长回文字符串，其中心肯定最靠近左侧。

希望这样可以清楚地解释您所询问的链接博客中的特定部分！我故意以多种方式重复自己，希望有所帮助。今天是荣格算法日：）

请注意，我专门并仅仅是试图澄清迈克尔所问的非常具体的问题。

简直太令人困惑了，不是吗？

顺便说一句，我只是忽略了字符上和字符下的中心问题-但这与理解您所询问的问题无关。