这是关于前段时间讨论的最长回文算法的问题。引用的解释该算法的博客文章说：“要选择下一个中心，取当前回文的最长回文真后缀的中心”。不幸的是，他们没有提供证据，我也不明白为什么下一个中心是当前回文的最长回文正确后缀的中心。
任何人都可以证明/解释它吗？
问问题
471 次
1 回答
5
所以我们向右移动...
假设你的“当前”回文是 40 个字母大。（可能以 100 号位置为中心。）您正试图找到一个更大的位置。
（好吧，可能有一个更大的，有 900 个字母长，右边是 50,000 个字母 - 完全不涉及这个。没关系。但我们会在未来解决这个问题。现在，我们有在寻找超过 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 的中心的左边。
最长的回文粘在右边，当然中心最靠近左边。
所以希望这能清楚地说明链接博客上讨论的具体部分，你问的！！！！我故意以多种方式重复自己，希望对您有所帮助。这是荣格算法日:)
再次请注意，我是专门且只是试图澄清迈克尔提出的非常具体的问题。
该死的混乱是吗？
顺便说一句，我只是忽略了角色中心的问题——但这与理解你所问的无关。
于 2010-12-09T15:31:26.857 回答