马拉车算法（我们一起种蘑菇！）--最长回文子串力扣--5

目录马拉车算法--种蘑菇题目分析解法一扩展中心优化法解法二马拉车算法java语言扩展中心优化版马拉车算法python语言扩展中心优化版马拉车算法马拉车算法--种蘑菇用于解决最长回文字串的线性方法也可以解决回文子串计数问题。题目给你一个字符串s找到s中最长的 回文 子串。示例 1输入s babad输出bab解释aba 同样是符合题意的答案。示例 2输入s cbbd输出bb提示1 s.length 1000s仅由数字和英文字母组成分析Q1什么是回文子串A1倒着读和正着读是一样的。解法一扩展中心优化法回文串一定是对称的所以我们可以每次循环选择一个中心进行左右扩展判断字符串是否相等但是这里出现一个问题如果是偶数个怎么办 即他的中心夹在两个中间所以在枚举的过程中不仅要枚举每一个字母还要枚举每一个夹缝所以进而想到在每一个字母的夹缝中以及开头和中间都添加一个不在字符集的#号这样可以把字母夹缝实体化而且和其他字母不重复不会改变其性质。而且它会把偶数个个变为奇数个因为它会把缝隙都填满且中心变为#号例如a b a b ——— # a # b # a # b #若原来是奇数个字母他插入以后仍是奇数个中心还为字母为了方便起见可以在字符串的最开头和最结尾处加上除了#号和字母的其他符号可以不用管循环的时候数组下标是否到达边界的情况不用判断下标是否合乎边界。用一个for循环去遍历所有可能的中心for循环会遍历所有可能的字母甚至#号同时向左和向右看直到他某一边的一个字母和他对称的位置是不一样的此时就找到了最长回文子串e.g.可以看到当到d的时候不一样了向左和向右分别走了3步且他的最长回文字串的长度: b c b也为3所以以中心为特征向左和向右分别扩展了几步就对应了原始的最长回文字符串有多长这种方法的时间复杂度为On^2解法二马拉车算法在解法一的基础上创建一个数组p来记录以某个字母为中心向左或者向右最远能够扩展多少次e.g.:我们开始种蘑菇蘑菇的伞盖大小标志着回文串的覆盖范围回文子串的左边和右边是完全一样的这是回文子串的对称性。如果我们接着往下画我们会发现大的伞盖的右侧和大的伞盖的左侧是完全对称的再接着往下画我们发现对于a而言是一个超级大蘑菇a的右侧可以照搬a的左侧但是在此处发现对于这个c而言不能照搬a左侧的情况它的蘑菇伞盖的长度有一节在a的覆盖范围以外如何解决呢由于a的覆盖范围有限所以我们可以假设c的覆盖范围至少有这么长刚好到达a的覆盖范围它可能比这个长度更长我们可以通过中心扩展法进一步将其向右推检查其右边和左边是否一致我们可以根据a的覆盖范围得到一个最小值至少能管到这个范围即a的覆盖范围实现线性复杂度Onjava语言扩展中心优化版class Solution { public String longestPalindrome(String s) { if (s null || s.length() 0) return ; StringBuilder sb new StringBuilder(); // 首尾加特殊符号不用判断越界 sb.append(^); for (char c : s.toCharArray()) { sb.append(#); sb.append(c); } sb.append(#); sb.append($); String newStr sb.toString(); int n newStr.length(); int maxCenter 0; // 记录最长回文的中心 int maxRadius 0; // 记录最长回文的半径 for (int i 1; i n - 1; i) { // 遍历所有可能的中心 int left i; int right i; while (newStr.charAt(left - 1) newStr.charAt(right 1)) { left--; right; } // 记录最长的 int currentRadius right - i; if (currentRadius maxRadius) { maxRadius currentRadius; maxCenter i; } } int start (maxCenter - maxRadius) / 2;//加了#长度被放大为原来的两倍 这样可以得到原字符串的下标左边的 int end start maxRadius; return s.substring(start, end); } }马拉车算法class Solution { public String longestPalindrome(String s) { String s2preProcess(s); int ns2.length(); int [] pnew int[n]; int c0;//中心点 int r0; for(int i1;in-1;i){ int i_mirror2*c-i;//刚开始i_mirror为-1复制p[1]为0即第一个#处为0 if(ri){//在覆盖范围内直接照抄镜子对面的 p[i]Math.min(r-i,p[i_mirror]); }/*else{ p[i]0; } 有没有都可以*/ while(s2.charAt(i1p[i])s2.charAt(i-1-p[i])){ p[i]; } if(ip[i]r){//刚开始100,中心点变为#r等于1 ci;//c一步一步往后移即中心一直往后 rip[i]; } } int maxl0; int center0; for(int i1;in-1;i){ if(p[i]maxl){ maxlp[i]; centeri; } } int start(center-maxl)/2; return s.substring(start,startmaxl); } public String preProcess(String s){ int ns.length(); if(n0){ return ; } String s1^; for(int i0;in;i){ s1#s.charAt(i); } s1#$; return s1; } }Q1i_mirror​2*c−i以及镜像点的作用A1:c 是中点中点公式cii_mirror)/2​​两边乘 22*cii_mirror​移项i_mirror​2*c−iC 镜子i 右边的你i_mirror 左边镜子里的你如果 i 还在大回文里面 右边 i 的回文长度 左边 i_mirror 已经算好的长度直接赋值不用扩你还没算镜子里的你早就算完了直接把他的答案拿过来用Q2r是什么A2r为遇到的蘑菇中翼展最靠右的蘑菇标志我探索到哪里了所以在i为1的时候要更新p[i],代表他探索到了下标1处python语言扩展中心优化版class Solution: def longestPalindrome(self, s: str) - str: if not s: return new_s ^ for c in s: new_s # c new_s #$ max_radius 0 # 最长回文半径 max_center 0 # 最长回文中心 n len(new_s) for i in range(1, n - 1): left i right i # 左右对称就继续扩 while new_s[left - 1] new_s[right 1]: left - 1 right 1 # 更新最长半径 radius right - i if radius max_radius: max_radius radius max_center i start (max_center - max_radius) // 2 end start max_radius return s[start:end]马拉车算法class Solution: def longestPalindrome(self, s: str) - str: s2 self.preProcess(s) n len(s2) p [0] * n c 0 # 中心点 r 0 for i in range(1, n - 1): i_mirror 2 * c - i if r i: p[i] min(r - i, p[i_mirror]) while s2[i 1 p[i]] s2[i - 1 - p[i]]: p[i] 1 # 更新中心和右边界 if i p[i] r: c i r i p[i] # 找最长回文 maxl 0 center 0 for i in range(1, n - 1): if p[i] maxl: maxl p[i] center i # 还原到原字符串 start (center - maxl) // 2 return s[start:start maxl] # 预处理加 ^ # $ def preProcess(self, s): n len(s) if n 0: return s1 ^ for i in range(n): s1 # s[i] s1 #$ return s1