算法作用：算出一个字符串中最长的回文子字符串 （有时也被表述成最长连续的子序列）
如果用最暴力的算法，就是确定一个字符串然后一点一点往两边找，最差情况就是整个字符串由一个字符形成，时间复杂度是O(n2)
manacher算法可以将时间复杂度变为O(n)
我们先明确一下什么是回文： 回文指的是从后往前读和从前往后读一致的字符串 例如：“aaaa”、“abba”、"ababa"等等
我们可以看到，回文分为字符数量为奇数的和字符数量为偶数的，下面就称作奇回文和偶回文
那么就算是上面提到的从每个字符一个一个往前后找的情况，面对奇回文和偶回文也要两种算法，不仅时间复杂度高而且需要写两套算法很复杂
manacher算法用一个很巧妙的算法解决了这个问题，将字符串的0下标和最后插入一个原字符串不可能存在的字符，然后字符之间也插入这个字符，这样设原字符长度为len的话，插入字符后的长度就变成2*len+1，长度直接变成奇数，那么我们只需要为奇回文的算法就行了
举例子：(假设插入字符’#’) 原字符串:“aabbaa”,长度为6 处理后:"#a#a#b#b#a#a#"，长度为13
原字符:“aaaaa”,长度为5 处理后:"#a#a#a#a#a#",长度为11
把处理之后的字符串存入一个字符数组中之后 我们还需要利用回文的对称性，进行一个处理 设立两个变量maxid和id， 设立一个辅助数组p[]记录处理后的字符串对应该字符的回文半径; maxid记录了搜索过程中找到的回文末端的最远距离 id记录了maxid对应的回文中心 例如:str[14]=“#a#a#b#b#a#a#"来说，
计数器 i 下标为1时，字符串对应字符是a，它对应的最长回文字符串是"#a#"，这个回文的字符串最长下标到了2，此时在计数器下标变为2之前maxid就变成了2，id就变成了1,p[1]变成了2；（整个过程看下图）
标黄色的7是在新字符串中最长回文串的半径，对于aabbaa这个偶字符串来说，答案出现在#这个插入字符下，奇字符串对应来说p[i]最大值出现在原本出现的字符下面
至于为什么这样操作，这利用了回文的对称性
如图所示，当i小于maxid的时候，i的回文半径可以通过id为中心的回文串的对称性得出这样一个结论，如果i + p[2id-i]小于maxid，那么以i为半径的回文串一定和不会小于P[2id-1]，（想不明白的话可以自己写一个字符串看下）
当然，如果i+p[i]大于maxid了，那么p[i]最多只能到maxid到i之间的距离，毕竟后面没搜索到啊
这样时间复杂度就降为O(n)了
那么我们找到了p[i]的最大值之后怎么确定原字符串的最长回文字符串的长度呢？
先说结论：p[i]-1
简单推导一下：
假如我们找到的新字符串中的最长回文串是 “#a#a#a#”（新字符串中半径最后一定是落到#上的），长度为7 那么p[i] = 4; 能一眼看出来原字符串回文是aaa，长度是3 因为7 = 2倍p[i]-1; 7 - 1= 6; 3 = 6 / 2; 那么3 = (2倍P[i]-1-1)/2; 也就是p[i]-1;
参考了两篇帖子 帖子1 帖子2
