Mic*_*ael 4 algorithm palindrome
这是一个关于前一段时间讨论的最长回文算法的问题.引用博客文章解释了算法,他说:"选择下一个中心,取目前回文中最长的回文正确后缀的中心".不幸的是,他们没有提供证据,我真的不明白为什么下一个中心是当前回文最长的回文正确后缀的中心.
任何人都可以证明/解释它吗？
所以我们正在向右移动......
说你的"当前"回文是40个大字母.(也许以位置100为中心.)你正试图找到一个更大的.
(好吧,可能会有一个更大的900字母长,那是右边的50,000个字母 - 完全没有涉及到这个.这很好.但是我们将来会做到这一点.现在,我们有在寻找40个以上的回文时,将中心向右移动.有道理吗？)
所以我们必须向右移动 - 我们可以迈出一步.但是我们想尽可能地移动而不会遗漏任何东西.
现在,如果右边的下一个要包括这个...事实上,它必须包括这组40 的最右边的字母.(它不能再向左,因为我们'已经检查过了,所以,它必须在100之后居中,并且,因为它将超过40,它必须包括我们的右手信,#120.)
那么我们还有多远呢？
好吧,你不能回到(从120)回到了回文!如果它不是中间的回文,它永远不会是回文.
3333333333333331110111
你只能"回"到0,坐在0左边的1(例如),永远不会是回文.
就这么简单. 你必须包括我们最正确的信件(如果我们要包括我们中的任何人),并且你希望它尽可能大,而且它必须是一个回文,因为回文只能开始(我的意思是"从中间")与回文.
在上面的例子中,无论我们后来在右边找到什么,左边的1或者0,或者说最右边的3,都不可能在这个宇宙中心的一个回文中.他们周围没有回文,所以他们"永远不会"成为回文中心!
请注意,3s中间的3可能是一个更大的回文.... 但不要忘记我们已经检查过这是迄今为止最长的回文(基于中心,从左边),所以不能是真的.
因此,任何比这个更长的回文 - 相比,下一个可能比这个更长的回文的起点 - 是0.
换句话说,它只是我们目前右侧最大的回文的中心.(所以,不是"111",它是回文而是短,但是"1110111"是你可以看到的最长的回文卡在右边.)
实际上,我们必须检查的两种可能性是(A)"0"和(B)倒数第二位的"1".当然,在这两种可能性中,我们必须从左到右,所以(A)"0"确实是下一个要检查的.
不要忘记那两个(有问题的0和1)相当于说"末尾有一个回文1110111,而且末尾有一个较短的回文111".
当然1110111更长,因此1110111的中心显然位于111的中心左侧.
最右边的回文粘在右边,当然会让中心最左边.
所以希望这清楚地说明了链接博客上讨论的具体部分,你问过!!! 我故意以多种方式重复自己,希望它有所帮助.这是Jungian算法日:)
再次请注意我是专门的,只是试图澄清迈克尔询问的非常具体的问题.
血腥混淆呃？
顺便说一句,我只是忽略了角色中角色中心的问题 - 但这与理解你所问的内容无关.