5:最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"输出: "bb"

一、法一暴力破解

这个就不用多解释了

class Solution {    /**     * 法一：     * @param String $s     * @return String     */    function longestPalindrome($s) {        $len = strlen($s);        $tmps = '';        $max = 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;                }            }        }        return $tmps;    }    function isPalindrome($subs){        $len = strlen($subs);        for($i=0; $i<(int)($len/2); $i++){            if($subs[$i] != $subs[$len-$i-1]){                return false;            }        }        return true;    }}

二、最长公共子串

思路：就是把字符串反转过来，例如 s=‘ababc’，反正s‘=’cbaba‘，两个字符串左右重合，得出最长的子串就是答案，也就是bab（或aba）。但是有可能会出现==特例（如：S = abc435cba，S' = abc534cba）==，重合，子串为abc。不符合条件，需要加判断

class Solution2 {    /**     * @param String $s     * @return String     */    function longestPalindrome($s) {        $len = strlen($s);        if($len == ''){            return $s;        }        $origin = $s;        $reverse = strrev($s);        $arr = [];        $maxLen = 0;        $maxStart = 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 会被判断为最小回文子串                     * 解：判断倒置前的子串下标，是否符合条件                     */                    if($arr[$i][$j] > $maxLen){                        $beforeJ = $len - $j - 1;                        if($beforeJ + $arr[$i][$j] -1 == $i){                            $maxLen = $arr[$i][$j];                            $maxStart = $i;                        }                    }                }else{                    $arr[$i][$j] = 0;                }            }        }        echo substr($s,$maxStart-$maxLen+1,$maxLen);    }}

三、中心拓展法

把每个字母当成回文串的中心。考虑两种情况，长度为奇数和偶数

class Solution3 {    /**     * @param String $s     * @return String     */    function longestPalindrome($s) {        $n = strlen($s);        if($n == ''){            return $s;        }        $start = 0;        $maxlen = 0;        for($i=0; $i<$n; $i++){            $len1 = $this->isPalindrome($s,$i,$i);//奇数            $len2 = $this->isPalindrome($s,$i,$i+1);//偶数            $len = max($len1,$len2);            if($len > $maxlen){                $start = $i - ($len-1)/2;                $maxlen = $len;            }        }        return substr($s,$start,$len) ;    }    function expend($str,$i,$j){        $n = strlen($str);        $l = $i;        $r = $j;        while($l>=0 && $r<$n && $str[$l] == $str[$r]){            $l-- ;            $r++ ;        }        return $r-$l-1;    }}

三、马拉车算法

重新组合字符串，将其变为奇数个。充分的利用回文串的对称性质，

class Solution4 {    /**     * @param String $s     * @return String     */    function longestPalindrome($s) {        $T = $this->malache($s);        $n = strlen($T);        $C = $R = 0;        $p = [];        for($i=1; $i<$n-1; $i++){            $i_mirror = $C*2 - $i;            if($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;        for ($i=1; $i<$n-1;$i++ ){            if($p[$i] > $maxLen){                $maxLen = $p[$i];                $centerIndex = $i;            }        }        $start = ($centerIndex-$maxLen)/2;        echo substr($s,$start,$maxLen);    }    function malache($str){        $n = strlen($str);        if(!$str){            return "^$";        }        $ret = '^';        for($i=0; $i<$n; $i++){            $ret .= '#'.$str[$i];        }        $ret .= "#$";        return $ret;    }}