algorithm - 最长回文算法如何选择下一个中心？

Question

这是关于 longest palindrome algorithm 的问题前段时间在这里讨论过。引用blog post解释了该算法，它说:“要选择下一个中心，请取当前回文的最长回文适当后缀的中心”。不幸的是，他们没有提供证明，而且我真的不明白为什么下一个中心是当前回文的最长回文专有后缀的中心。 p>

谁能证明/解释一下？

Answer 1

所以我们向右移动...

假设您的“当前”回文有 40 个字母大。 (也许以位置 100 为中心。)您正试图找到更大的位置。

(好吧，可能有一个更大的，有 900 个字母长，右边有 50,000 个字母 -- 完全不涉及这个。没关系。但我们会在未来解决这个问题。现在，我们必须将中心向右移动，同时寻找超过 40 个回文。有意义吗？)

所以我们必须向右移动 - 我们可以移动一步。但是我们想尽可能地移动而不遗漏任何东西。

现在，如果右边的下一个要包含这个...事实上，它必须包含这个组的最右边的字母 40。(它不能再靠左了，因为我们已经检查过了，所以，它必须在 100 之后居中，而且，因为它会长于 40/strong>，它必须包括我们右边的字母，#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中心的左边。

最长的回文落在右边，当然中心离左边最近。

因此，希望这能清楚地说明链接博客上讨论的特定部分，您问的是哪个!!!我故意以多种方式重复自己，希望它有所帮助。今天是荣格算法日 :)

再次请注意，我只是明确地尝试澄清 Michael 询问的非常具体的问题。

该死的令人困惑吧？

顺便说一句，我只是忽略了字符外中心的问题 - 但它与理解您所问的内容无关。