5：最长回文子串给定一个字符串s，求s中最长的回文子串。您可以假设s的最大长度为1000。示例1：输入：“babad”输出：“bab”注意：“aba”也是一个有效答案。示例2：输入："cbbd"输出："bb"1.方法一暴力破解，这个不用解释classSolution{/***方法一：*@paramString$s*@returnString*/functionlongestPalindrome($s){$len=strlen($s);$tmps='';$最大值=0;for($i=0;$i<$len;$i++){//起始下标for($j=$i+1;$j<=$len;$j++){//长度if($this->isPalindrome(substr($s,$i,$j))&&$j>$max){$tmps=substr($s,$i,$j);$max=$j;}}}返回$tmps；}functionisPalindrome($subs){$len=strlen($subs);for($i=0;$i<(int)($len/2);$i++){if($subs[$i]!=$subs[$len-$i-1]){返回假；}}返回真；}}2.最长公共子串思路：将字符串反转，比如s='ababc'，反正s'='cbaba'，两个字符串左右重叠，最长子串就是答案。那是bab（或aba）。但是可能会有==特例（比如：S=abc435cba,S'=abc534cba）==，巧合的是，子串是abc。不满足条件，需要加判断classSolution2{/***@paramString$s*@returnString*/functionlongestPalindrome($s){$len=strlen($s);如果（$len==''）{返回$s;}$原点=$s;$reverse=strrev($s);$arr=[];$最大长度=0;$最大开始=0;for($i=0;$i<$len;$i++){//原字符串下标for($j=0;$j<$len;$j++){//反转字符串下标if($origin[$i]==$reverse[$j]){if($i==0||$j==0){$arr[$i][$j]=1;}else{//状态转移方程$arr[$i][$j]=$arr[$i-1][$j-1]+1;}/***用于避免特殊情况*例如：S=abc435cba,S'=abc534cba*不做特殊处理，abc会被判断为Minimalpalindromesubstring*解决方法：判断反转前子串的下标是否满足条件*/if($arr[$i][$j]>$maxLen){$beforeJ=$len-$j-1;如果($beforeJ+$arr[$i][$j]-1==$i){$maxLen=$arr[$i][$j];$maxStart=$i;}}}else{$arr[$i][$j]=0;}}}echosubstr($s,$maxStart-$maxLen+1,$maxLen);}}三、中心展开法把每个字母作为回文的中心考虑两种情况，长度为奇数和偶数classSolution3{/***@paramString$s*@returnString*/functionlongestPalindrome($s){$n=strlen($s);如果（$n==''）{返回$s;}$开始=0;$最大长度=0;for($i=0;$i<$n;$i++){$len1=$this->isPalindrome($s,$i,$i);//奇数$len2=$this->isPalindrome($s,$i,$i+1);//偶数$len=max($len1,$len2);如果($len>$maxlen){$start=$i-($len-1)/2;$maxlen=$len;}}返回substr($s,$start,$len);}functionexpend($str,$i,$j){$n=strlen($str);$l=$i;$r=$j;while($l>=0&&$r<$n&&$str[$l]==$str[$r]){$l--;$r++;}返回$r-$l-1;}}三、马拉车算法将字符串重新组合，变成奇数。填充的利用回文串的对称性质，classSolution4{/***@paramString$s*@returnString*/functionlongestPalindrome($s){$T=$this->malache($s);$n=strlen($T);$C=$R=0;$p=[];for($i=1;$i<$n-1;$i++){$i_mirror=$C*2-$i;如果($R>$i){$p[$i]=min($R-$i,$p[$i_mirror]);}else{$p[$i]=0;}while(($T[$i-1-$p[$i]])==($T[$i+1+$p[$i]])){$p[$i]++;}if($i+$p[$i]>$R){$C=$i;$R=$i+$p[$i];}}$maxLen=0;$centerIndex=0;对于($i=1;$i<$n-1;$i++){if($p[$i]>$maxLen){$maxLen=$p[$i];$centerIndex=$i;}}$start=($centerIndex-$maxLen)/2;echosubstr($s,$start,$maxLen);}函数malache($str){$n=strlen($str);如果（！$str）{返回“^$”；}$ret='^';for($i=0;$i<$n;$i++){$ret.='#'.$str[$i];}$ret.="#$";返回$ret；}}
