题解 | #最长回文子串#

题解一： 动态规划
图示：dp[i][j]表示A[i:j] 是否为回文串

复杂度分析：
时间复杂度：O(N^2)
空间复杂度：O(N^2)
实现如下：

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int dp[n][n]; // dp[i][j] 表示A[i:j] 是否是回文串
        int max_len = 0;  //最长回文子串的长度
        memset(dp, 0, sizeof(dp));
        //从尾到头
        for(int i = n-1;i>=0; i--){
            //从左到右
            for(int j = i;j<n;j++){
                int len  = j-i+1; //子串长度
                if(A[i]==A[j]){   // 如果A[i],A[j]相等
                    dp[i][j] = len<=2 ? 1 : dp[i+1][j-1];  //len<=2那么就为回文串，len>2： dp[i][j] = dp[i+1][j-1]
                }
               if(dp[i][j]) max_len = max(max_len,len); //如果A[i:j] 为回文串，那么就从maxlen与len之间取大的
            }
        }
        return max_len;
    }
};

题解二：中心扩散
思路： 以一个字符为中心向两边扩散，找出以该字符为中心的最长回文串。
图示：情况a: 回文串长度为奇数； 情况b:回文串长度为偶数

复杂度分析：
时间复杂度：O(N^2)
空间复杂度：O(1)
实现如下：

class Solution {
public:
    //向两边扩散，返回最长回文串长度
    int kuosan(const string &A,int left,int right,const int &n){
        while(left>=0&&right<n&&A[left]==A[right])
        {
            left--; right++;  //向两边扩
        }
        return right-left-1;
    }

    int getLongestPalindrome(string A, int n) {
        int max_len = 0;
        for(int i = n-2;i>=1;i--) //中心位置，注意中心点不会选在0-1之间的中心点，所有循环之后还需要判断中心点选择0-1之间子串
        {
            int len_1 = kuosan(A,i-1,i+1,n); // 回文串长度为奇数的扩散
            int len_2 = kuosan(A,i,i+1,n); // 回文串长度为偶数的扩散，选取i与i+1的中间为扩散开始点
            int len = max(len_1,len_2);  //取奇数长度回文串和偶数长度回文串
            max_len = max(len,max_len);   //最后判断max_len与len大小
        }
        if(A[0]==A[1] && max_len<2) max_len = 2; //判断中心点选择0-1之间子串
        return max_len;
    }
};

题解三：Manacher
题解思路：Manacher利用了回文串的对称性，插入特殊符号将偶回文串变为奇回文串（如：abba----> #a#b#b#a），并且用一个p数组(半径数组)记录字符串中的字符向左向右扩展的长度。
图示：

计算半径数组p:

复杂度分析：
时间复杂度：O(N) : 只匹配未匹配的位置，对于字符串每个位置只匹配一次。
空间复杂度：O(N)

实现如下：

class Solution {
public:
    void manacher(string s,int n,vector<int>& p){
        int m = 0;
        int m_r = 1; //当前计算回文串的最右端
        for(int i = 1;i<n;i++){
          if(m_r>i) p[i] = min(p[2*m-i],m_r-i); // 情况1 ： 解释： 2*m-i;  m到i的距离为i-m. j的位置为 m-(i-m) = 2*m-i;
          for(;(s[i+p[i]]==s[i-p[i]] && (i-p[i]>=0)&&(i+p[i]<2*n+1));p[i]+=1){  // 以i点向两边扩展
            if(m_r < i + p[i]) //情况1中 p[j] > m_r-i
            {
                m_r = i+p[i];  //更新最右端值
                m = i; //更新m
            }
            }
        }
    }
    int getLongestPalindrome(string A, int n) {
        int max_len = 0;
        string s="";   // 存储插入特殊字符之后的字符串
        vector<int> p(2*n+1,1);
        for(int i = 0;i<2*n+1;i++)  //插入特殊字符
        {
           s.push_back('#');  
           s.push_back(A[i/2]);++i; 
        }
        manacher(s, 2*n+1, p);
        for(auto i : p){
            max_len = max(max_len,i-1);  //取最大的
        }
        return max_len;
    }
};