定义：如果一个字符串正着读和反着读是一样的，那它就是回文串

　　　例如：aba 、 abba 不限制奇数偶数

判断是否是回文字符串

　　思路：从最前后各去一个做对比，如果相同则进行下一个，直到相挨为止

function palindrome($str) {    $i = 0;    $j = strlen($str)-1;    $flag = 1;    while($i<$j)    {        if($str[$i] != $str[$j])        {            $flag = 0;            break;        }        $i++;        $j--;    }        return $flag;    }

 

计算最长回文字串

方法1：

　　暴力破解：计算出每个可能的字串，然后对比   

　　时间复杂度:n(n^3)

function findLongestPalindrome($str){    $palindrome = array();        for($i=0;$i

 

方法2：中心扩展

中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。

但是要考虑两种情况：

1、像aba，这样长度为奇数。

2、想abba，这样长度为偶数。

function findLongestPalindrome($str){    $maxLen = 0;        for($i=0;$i
     
      =0 && $right
      
       $maxLen)            {                $maxLen = $right-$left+1;            }                        $left --;            $right ++;                    }    }        return $maxLen;    }
      
     

 

方法3：Manacher

　　1、奇偶数的问题，在字符串两边和中间分别插入特殊符号（如：#） 后，没个字符串都为奇数（奇数+偶数=奇数）

　　2、重复访问问题，根据回文字符串的对称性快速扩展回文串

function findLongestPalindrome($str){    //预处理，字符中间和两边增加#字符    $strArr = str_split($str);        $str = '#'.implode('#', $strArr).'#';        $maxLen = 0;        $rl = array();//记录以该字符为中心的最长回文字符串半径    $maxRight = 0;//现在访问到的最右边的字符    $pos = 0; //$maxRight位置对应的轴位置        for($i=0;$i
     
      =0 && $i+$rl[$i]
      
       $maxRight)        {            $maxRight = $i+$rl[$i]-1;            $pos = $i;        }                $maxLen = max($maxLen, $rl[$i]);    }        return $maxLen - 1;}
      
     

 

参考：