python字符串中最长的连续升序⼦串_求最长回⽂⼦串算法
——马拉车算法
Manacher's Algorithm，中⽂名叫马拉车算法，是⼀位名叫Manacher的⼈在1975年提出的⼀种算法，解决的问题是求最长回⽂⼦串，神奇之处在于将算法的时间复杂度精进到了O(N)，下⾯我们来详细介绍下这个算法的思路。
01 算法由来
在求解最长回⽂⼦串的问题时，⼀般的思路是以当前字符为中⼼，向其左右两边扩展寻回⽂，但是这种解法的时间复杂度是O(N^2)，那么能不能将时间复杂度再降低⼀点？做到线性？马拉车算法就完美地解决了这个问题。
02 预处理
回⽂字符串以其长度来分，可以分为奇回⽂(其长度为奇数)、偶回⽂(其长度为偶数)，⼀般情况下需要分两种情况来寻回⽂，马拉车算法为了简化这⼀步，对原始字符串进⾏了处理，在每⼀个字符的左右两边都加上特殊字符(肯定不存在于原字符串中的字符)，让字符串变成⼀个奇回⽂。例如：
原字符串：abba，长度为4 预处理后：#a#b#b#a#，长度为9
原字符串：aba，长度为3 预处理后：#a#b#a#，长度为7
03 计算最长回⽂⼦串长度
以字符串"cabbaf"为例，将预处理后的新字符串"#c#a#b#b#a#f#"变成⼀个字符数组arr，定义⼀个辅助数组int[] p，p的长度与arr等长，p[i]表⽰以arr[i]字符为中⼼的最长回⽂半径，p[i]=1表⽰只有arr[i]字符本⾝是回⽂⼦串。
i      0 1 2 3 4 5 6 7 8 9 10 11 12arr[i]  # c # a # b # b # a #  f  #p[i]    1 2 1 2 1 2 5 2 1 2 1  2  1
我们来⽐对分下⼀下最长回⽂半径和原字符串之间的关系。在上⾯例⼦中，最长回⽂⼦串是"#a#b#b#a#"，它以arr[6]为中⼼，半径是5，其代表的原始字符串是"abba"，⽽"abba"的长度为4，可以通过5减去1得到，是字符串"cabbaf"中的最长回⽂⼦串，那么我们是不是可以得出最长回⽂半径和最长回⽂⼦串长度之间的关系？
让我们再多看⼏个例⼦，如"aba"，转换后是"#a#b#a#"，以字符'b'为中⼼的回⽂，半径是4，减1得到3，3是原字符串的最长回⽂⼦串长度。
再例如"effe"，转换后是"#e#f#f#e#"，以最中间的'#'为中⼼的回⽂，半径是5，减1得到4，4是原字符串的最长回⽂⼦串长度。
因此，最后我们得到最长回⽂半径和最长回⽂⼦串长度之间的关系：int maxLength = p[i]-1。maxLength表⽰最长回⽂⼦串长度。
04 计算最长回⽂⼦串起始索引
知道了最长回⽂⼦串的长度，我们还需要知道它的起始索引值，这样才能截取出完整的最长回⽂⼦串。
继续以第三步中的字符串"cabbaf"为例，p[6]=5，是最长半径，⽤6(i)减去最长半径5(p[i])得到1，⽽1恰好是最长回⽂⼦串"abba"的起始索引。
我们再来看⼀个奇回⽂的例⼦。例如"aba"，转换后是"#a#b#a#"，p[3]=4，最长半径是4，i为3，⽤i减去4得到-1，数组下标越界了。
在偶回⽂的情况下，可以满⾜i减最长半径，⽽奇回⽂却会下标越界，我们需要在转换后的字符串前⾯再加⼀个字符，解决下标越界的问题，不能是'#'，那就加个'$'字符吧，但是加过⼀个字符后，字符串的长度不是奇数了，只能在尾部再加⼀个不会重复出现的字符，⽐如'@'，这样字符串的长度依旧是奇数了，满⾜前⾯第三部分的条件。
加多⼀个字符后，奇回⽂可以正常做减法了，偶回⽂呢？
i      0 1 2 3 4 5 6 7 8 9 10 11 12 13arr[i]  $ # c # a # b # b # a  #  f  #p[i]      1 2 1 2 1 2 5 2 1 2  1  2  1
在补上字符'$'后，p[7]=5，⽤i减去最长半径，7-5=2，⽽理想的结果应该是1，那就再除以2吧，这样就能得到1了。⽽奇回⽂"aba"在⽤i 减去最长半径后得到的是0，除以2后还是0，可以完美解决下标越界的问题。
结论：最长回⽂⼦串的起始索引int index = (i - p[i])/2。
05 计算p数组
在第三步和第四步中我们都⽤到了⼀个关键对象p数组，存放的是最长回⽂⼦串半径，那么它是怎么来的呢？ 还是以上⾯的例⼦配合着看，i      0 1 2 3 4 5 6 7 8 9 10 11 12 13 14arr[i]  $ # c # a # b # b # a  #  f  #  @ p[i]      1 2 1 2 1 2 5 2 1 2  1  2  1
设置两个变量id和mx，id是所有回⽂⼦串中，能延伸到最右端位置的那个回⽂⼦串的中⼼点位置，mx是该回⽂串能延伸到的最右端的位置。
当i等于7时，id等于7，p[id] = 5，在以位置7为中⼼的回⽂⼦串中，该回⽂⼦串的右边界是位置12。
当i等于12时，id等于12，p[id] = 2，在以位置12为中⼼的回⽂⼦串中，该回⽂⼦串的右边界是位置14。
由此我们可以得出回⽂⼦串右边界和其半径之间的关系：mx = p[id]+id。
image
python获取数组长度因为回⽂字符串是中⼼对称的，知道中⼼点位置id，如果⼀个位置的回⽂⼦串以i为中⼼，并且包含在以id为中⼼的回⽂⼦串中，即mx > i，那么肯定会存在另外⼀个以j为中⼼回⽂⼦串，和以i为中⼼的回⽂⼦串相等且对称，即p[j] = p[i]，⽽i和j是以id为中⼼对称，即i+j=2*id，如果知道了i的值，那么j = 2*id - i。
但是我们需要考虑另外⼀种情况，如果存在⼀个以i为中⼼的回⽂⼦串，依旧有mx > i，但是以i为中⼼的
回⽂⼦串右边界超过了mx，在i到mx的这段回⽂⼦串中，与另⼀端对称的以j为中⼼的回⽂⼦串还是相等的，此时p[i] = mx - i，p[j] = [pi]，⾄于右边界mx之外的⼦串，即以i为中⼼的回⽂⼦串超出的部分是否还是满⾜上述条件就需要遍历⽐较字符了。
因此，在mx > i的情况下，p[i] = Math.min(p[2*id - i], mx - i)。 另外如果i⼤于mx了，也即是边界mx后⾯的⼦串，依旧需要去⽐较字符计算。
06 ⼩结
马拉车算法将求解最长回⽂⼦串的时间复杂度降低到了O(N)，虽然也牺牲了部分空间，其空间复杂度为O(N)，但是其算法的巧妙之处还是值得学习和借鉴的。
算法专题⽬前已连续⽇更超过六个⽉，算法题⽂章211+篇，对话框回复【数据结构与算法】、【算法】、【数据结构】中的任⼀关键词，获取系列⽂章合集。
以上就是全部内容，如果⼤家有什么好的解法思路、建议或者其他问题，可以下⽅留⾔交流，好看、留⾔、转发就是对我最⼤的回报和⽀持！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。