书接上回，我们今天继续来聊聊最长回文子串的马拉车解法。
题目：给你一个字符串s，找到s中最长的回文子串。
01、中心扩展法优化-合并奇偶处理
俗话说没有最好只有更好，看着O(n^2)的时间复杂度，想想应该还有更优的方案吧，答案是肯定的，马拉车法就可以做到时间和空间复杂度都是O(n)。
其实无论什么算法都是为了解决某种问题而产生的，因此我们还是循序渐进地来优化中心扩展法最终得到马拉车法。
我们知道在中心扩展法中有一个很明显的问题：回文串长度奇偶性需要不同的处理方式，并且在计算之前我们也不知道这个回文串到底是奇还是偶，导致每次我们都需要同时求出奇偶两种情况下的回文串并取最大的那个，因此我们需要首先解决奇偶性导致的差异化处理问题。
如果要解决这个问题可能要从两个方面入手：其一从外部下手找到一个公式统一奇偶性，其二从内部下手修改自身使其变得统一。
关于第一点，因为本题的特点是根据奇偶性做不同的处理，而统一的公式更偏向一个值可以是奇或偶最后得到统一的结果，比如7和8，(7-1)/2=3，(8-1)/2=3，因此第一点并不适合本题。
关于第二点，奇数个字符之间有偶数个空格，偶数个字符之间有奇数个空格，而奇数加偶数还是奇数，也就是如果我们把这些空格考虑进来，奇偶性就统一了，那么接下来还有分析一下这个空格引入后是否会对原回文串特性产生影响，其实并没有影响，对于奇数串相当于中心元素两边各多了一个空格还是对称的，对于偶数相当于中心的两个元素之间加了一个空格结果也还是对称的，因为空格比较特殊，我们选择一个其他特殊符号比如[#]，因此这个方案具有可行。
这个方案还有最后一个小问题，就是怎么计算回文串长度，即实现通过处理后的字符串计算出实际的字符长度。
比如上图中原奇数回文串长度是5，处理后长度是11，原偶数回文串长度是6，出来后是13，如果我们不考虑中心元素i，则回文串实际长度正好等于处理后的一半，即原回文串长度=（处理后回文串长度 - 1）/2，我们先给这个值取个名字方便后面交流，叫回文串半径。
到这里优化方案就是确定了，解决了奇偶性问题，解决了字符串处理后转换问题，下面我们看看具体实现代码。
时间复杂度：O(n^2)，由于每遍到一个字符，都需要往左/右进行探测，所以是O(n^2)。
空间复杂度：O(1)。
因此这次优化性能上并没有任何提升，只是处理方式上做了优化，这一步并不是白做，而是为了下面马拉车法做前期准备。
02、中心扩展法再优化（马拉车法）
再暴力破解法优化中我们用到了经典的以空间换时间的做法，把已经计算过的子字符串结果存储下来减少了不必要的计算，同样的我也可以用类似的思想来优化中心扩展法。
暴力破解法用了回文串对称性由外向内判断是否是回文串，中心扩展法用了回文串对称性由内向外判断是否是回文串，而这两种方法都是应用了对称性去算，那么我们能否直接用回文串的对称性直接判断是否为回文串呢？答案是肯定的，下面我们用图例来说明其中原理。
在上面的合并奇偶处理中，我们知道处理后回文串半径长度就是我们最终回文串长度。如果我们把已经计算过的回文串半径存储下来，后面需要的时候就可以直接拿过来用了。
如上图，在回文串半径行中，绿色背景表示已经计算完回文串半径的字符，并中心扩展是从左往右计算的，此时计算完了s[9]即字符c处，那么我们想象一下此时如何计算索引为10即s[10]元素的回文串半径呢？s[11]、s[12]呢？
回想一下上文提到的对称性，如果我们以当前位置s[9]为中心点，那么其右半径和其左半径是对称的，也就是说相对应的元素应该是性质相同的，可以合理猜测s[10]应该和s[8]的回文串半径一致也为0，同理猜测s[11]=s[7]=1，s[12]=s[6]=2。
当然这并不绝对，我们只是想拿来说明我们可以利用对称性，把其对称点已经计算过的结果利用上，虽然上面的s[10]，s[11]，s[12]三个值是对的，但描述并不准确，因为存在s[10]>s[8]的情况。如下图：
如上图，当上一次处理完s[7]，可得其回文串半径为3，此时开始计算s[8],使用对称性可得s[8]>=s[6],因此我们在计算以s[8]为中心向两边扩展查找回文串时不需要再以s[8]为起点了，而是根据s[6]=2,我们直接跳跃2位，左边从s[6],右边从s[10],开始向两边扩展查找以s[8]为中心的实际回文串长度，最后计算可能为4，这一步正是整个算法的核心所在。
因此我们可以把这个算法分为两种情况：
（1）当前位置大于当前已探测右侧最远位置，则直接使用中心扩展方法查找回文串；
（2）当前位置小于等于当前已探测右侧最远位置，则根据其对称位置已计算结果，进行直接选择跳过部分位再开始使用中心扩展方法查找回文串；
当然起始位置、已探测最右侧位置、中心点、最大长度怎么选，什么时候更新，跳过多少位后再计算，这些都是细节部分了，我们下面直接看代码。
时间复杂度：O(n)，可能比较难以理解的是为什么for嵌套了while还是O(n)的时间复杂度？因为首先每个字符最多只会进行一次扩展，其次当进行一次新的扩展后，当前位置到最新的有边界这部分可以通过对称性得到而不需要再次扩展，因此while总的操作次数不会大于n，再加上预处理字符串n，以及初始化的辅助数组2n+1，因此整体还是O(n)。
空间复杂度：O(n)，我们需要 O(n) 的空间记录每个位置的半径。
这就是马拉车算法的整个过程，我们再来总结一下，马拉车算法是对中心扩展法的优化，解决了其两个问题：其一奇偶统一处理，其二利用对称性减少重复计算。其中第二点的重点是通过对称性不用每次扩展都从中心点出发，而是直接跳过已计算的部分位。
热门跟贴