Manacher算法（马拉车算法）时间复杂度O（n）
用过中心检测法（就是上面说的O(n2) O(n^2)O(n
)的算法）的都知道对于奇数回文串和偶数回文串的处理是不同的，奇数回文串有2n+1 2n+12n+1个字符，所以中心字符一定只有一个。而同理，对于偶数回文串，中心字符有2个。这样1个和2个的情况不好处理，所以我们将给出的串统一转化为奇数回文串。我们将每一个字符的左边和右边都添加一个字符（这个字符是输入中所没有的）。一般都为#。比如说abc和abcd这两个串转化后就为#a#b#c#和#a#b#c#d#。长度分别为7 77和9 99这样无论奇偶都能被转换成奇数回文串了.
其实在我看来,Manacher就是优化后的中心检测法,和KMP算法类似,Manacher的思想也是避免"匹配"失败后的下标回退
下面正式开始分析算法
首先,我们需要了解一个叫做回文半径的东西
当前循环到i=0
当前元素为=#
当前最大回文半径R=0
当前中心位置flag=0
当前最大半径r=1
=============================
当前循环到i=1
当前元素为=a
当前最大回文半径R=2
当前中心位置flag=1
当前最大半径r=2
=============================
当前循环到i=2
当前元素为=#
当前最大回文半径R=2
当前中心位置flag=2
当前最大半径r=2
=============================
当前循环到i=3
当前元素为=b
当前最大回文半径R=6
当前中心位置flag=3
当前最大半径r=4
=============================
当前循环到i=4
当前元素为=#
当前最大回文半径R=6
当前中心位置flag=3
当前最大半径r=4
=============================
当前循环到i=5
当前元素为=a
当前最大回文半径R=6
当前中心位置flag=5
当前最大半径r=4
=============================
当前循环到i=6
当前元素为=#
当前最大回文半径R=12
当前中心位置flag=6
当前最大半径r=7
=============================
当前循环到i=7
当前元素为=a
当前最大回文半径R=12
当前中心位置flag=6
当前最大半径r=7
=============================
当前循环到i=8
当前元素为=#
当前最大回文半径R=12
当前中心位置flag=6
当前最大半径r=7
=============================
当前循环到i=9
当前元素为=b
当前最大回文半径R=12
当前中心位置flag=9
当前最大半径r=7
=============================
当前循环到i=10
当前元素为=#
当前最大回文半径R=12
当前中心位置flag=9
当前最大半径r=7
=============================
当前循环到i=11
当前元素为=a
当前最大回文半径R=12
当前中心位置flag=11
当前最大半径r=7
=============================
当前循环到i=12
当前元素为=#
当前最大回文半径R=12
当前中心位置flag=12
当前最大半径r=7
=============================
6