马拉车算法，其实并不难!!!

马拉车算法其实不难！！！更多，往下看：题目描述给你一个字符串s，求s中最长的回文子串。示例示例1：输入：s="babad"输出："bab"解释："aba"也是符合题意的答案。示例2：输入：s="cbbd"输出："bb"示例3：输入：s="a"输出："a"示例4：输入：s="ac"输出："a"马车算法ThisIt是一个很棒的算法。它是1957年一个叫Manacher的人发明的，所以叫Manacher算法。主要用于寻找字符串中最长的回文子串。该算法最大的贡献是增加了时间复杂度。对于线性，我们前面提到的动态规划的时间复杂度是O(n2)。上面提到的中心扩展方法中，中心可能是一个字符，也可能是字符之间的空隙，所以如果有n个字符，就会有n+n+1个中心：为了解决中心可能是空隙的问题上面提到，我们去每个字符之间插入“#”，为了让展开的结束边界更清晰，在左边界插入“^”，在右边界插入“$”：S的意思为了在String后面插入“#”、“^”、“$”等符号，我们用一个数组P来表示S中每一个字符的长度，可以向两边扩展：比如P[8]=3，表示可以向两边扩展3个字符，即回文串的长度为3，去掉#后面的字符串为aca：P[11]=4，表示可以向两边扩展4个字符sides，即回文串的长度为4，去掉#后的串为caac：假设我们已经知道数组P，那么如何得到回文串呢？用P的下标索引减去P[i]（即回文串的长度）得到展开串S中回文串首字符的下标，除以2得到下标在原始字符串S.字符串中的下标。那么现在的问题是：如何求解数组P[i]其实马拉车算法的关键在于：它充分利用了回文串的对称性，利用已有的结果来帮助计算随后的结果。假设已经计算出字符索引位置P处的最大回文串，左边界为PL，右边界为PR：那么当我们找到一个位置i时，i小于等于PR，其实我们可以找到i关于Pj的对称点：那么假设以j为中心的最长回文串的长度为len，并且在PL到P的范围内，那么以i为中心的最长回文串的长度为：以i为中心的最长回文子串的长度等于以j为中心的最长回文子串的长度但是这里有两个问题：前一个回文串P是哪一个？有哪些特殊情况？特殊情况如何处理？(1)前面的回文串P指的是右边界之前计算出的最右边的回文串，因为它最有可能覆盖我们现在要计算的以i为中心的索引，我们可以复用前面结果的对称性。正因如此，我们在计算的时候，每次计算都需要不断更新P的中心和右边界。(2)特殊情况是当前i的最长回文串的计算不能再利用点P的对称性，例如：i的回文串右边界超过P的右边界PR：解这种情况的是的：多余的部分需要按照中心扩容法逐一扩容。i不在以P为中心的回文串中，只能按中心展开法处理。具体代码实现如下：//构造一个字符串publicStringpreProcess(Strings){intn=s.length();如果（n==0）{返回“^$”；}字符串ret="^";for(inti=0;ii){//i在右边界范围内，看i的对称点的回文串长度，i到右边界的长度，取小者//不能溢出之前的边界，否则必须扩大中心P[i]=Math.min(right-i,P[mirror]);}else{//超出范围，中心扩大P[i]=0;}//中心扩展while(S.charAt(i+1+P[i])==S.charAt(i-1-P[i])){P[i]++;}//看新索引是否大于之前保存的最右边界的回文串应该在右边if(i+P[i]>right){//updatecentercenter=i;//更新右边界right=i+P[i];}}//通过回文长度数组找到最长的回文串intmaxLen=0;int中心索引=0;对于(inti=1;imaxLen){maxLen=P[i];中心索引=我；}}intstart=(centerIndex-maxLen)/2;返回str.substring(start,start+maxLen);}至于算法的复杂度，空间复杂度取决于大小n的数组是O(n)，时间复杂度好像是用了两层循环，其实不是O(n2)，而是O(n)，因为大部分索引位置会直接使用前面的结果和对称性结果，可以得到常数次，而需要中心扩展的，因为超出了前面结果覆盖的范围，所以需要扩展。扩容得到的结果有利于计算下一个指标位置，所以扩容其实少【作者】：公众号【秦淮杂货店】作者秦淮，技术之路不是临时的，山高水长，再慢也不会停下脚步。个人写作方向：Java源码分析、JDBC、Mybatis、Spring、redis、分布式、简知Offer、LeetCode等，认真写好每篇文章，不喜欢头条党，不喜欢花里胡哨，多写系列的文章，不保证我写的是完全正确的，但我保证我写的是经过实践或搜索过的资料。如有遗漏或错误，敬请指正。剑指提供所有问答PDF2020年我写了什么？开源编程笔记