博客已经搬家，请前往 阅读格式良好的文章。
本文将一步一步构造Manacher算法，心急的一定看不懂！请先练习下面的习题。探索最长回文串性质题1：已知字符串以center为中心对称，求完整的字符串。abcd??? |center答abcdcba |center题2：接上题，abcdcba后面还有一些字符，以center2为中心，最大对称半径[ref]半径大于等于1。[/ref]为7，求完整的字符串。
答根据center2的对称性质，可以知道字符串为
abcdcba???abcdcb??
又根据center2最大对称半径为7，而不是8，所以c后面一定不是b（标识为b）。center3的对称半径确定！而且，center关于center2的对称点center3的索引号为center2*2-center=8*2-3=13。对称半径为center2+7-center3=8+7-13=2。
题3：稍微调整上题，若center2在a，对称半径为8，，求完整的字符串和center3的对称半径。
答：字符串为
babcdcbabcdcbab?
center3=center2*2-center=7*2-4=10。对称半径为center2+8-center3=7+8-10=5。这样对吗？
看起来半径不正确！应该同center一样都是4。问题出在哪里呢？明明用的是跟题2一样的公式啊！因为题2跟题3情况不同。题2 center左边超出了center2的对称范围；而题3 center左边没超出center2的对称范围。center3的半径确定。题4：同样，center在x，半径为2，center2在a，半径为5。求完整的字符串和center3半径。
答：根据center2的对称性补全center2范围内的字符。又因为center2的对称半径为5而不是6，索引11位的字符不是c。
ccdxdbab7dxdc11?12????
所以center3的半径就是2了吗？不一定哦！因为我们只知道索引11位的字符不是c，但它可能是b，这样就与索引7位的b匹配，对称半径达到3。同样地，我们也不知道索引12位的字符是什么。所以，在center和center2的左边界重合时，我们只知道center3半径的最小值。根据这三道例题，我们已经总结出回文字符的半径性质：在情况1、2中，求的是确切值，所以即使center3内含于多个对称范围，每个对称范围求出的半径都一定是一样的。在情况3中，所有对称范围的计算值的最大值是center3半径的最小值。
生活若剥去理想、梦想、幻想，那生命便只是一堆空架子
