题解

题目难度：中等难度、经典题目
知识点：字符串、动态数组、动态规划、Manacher法。
##名词解释：
1.子串：由原字符串中任意个连续字符组成的子序列，其长度小于等于原字符串长度。

2.回文：字符对称的文法，有“aba”(单核)和“cabbac”(双核)两种情况。

3.最长回文子串：首先寻找回文子串，其次，判断该回文子串是否为长度最长。

方法一（暴力求解）

思想：从最长的子串开始，遍历所有该原字符串的子串；每找出一个字符串，就判断该字符串是否为回文；子串为回文时，则找到了最长的回文子串，因此结束；反之，则继续遍历。

时间复杂度O(n^3)：遍历字符串子串：嵌套一个循环、O(n^2)， 判断是否为回文：再次嵌套一个循环、O(n^3)。

#include<iostream>
using namespace std;
string longesPlindrome(string s){
    if(s.length()<=1) return s;
    //i表示子串长度 
    for(int i=s.length();i>1;i--){ 
        //j表示子串从原字符串那个下标开始  
        for(int j=0;j<=s.length()-i;j++){
            string sub ;
            //得到子串 
            sub=s.substr(j,i);
            int count=0;
            //判断子串是否为回文字符串 
            for(int k=0;k<sub.length()/2;k++){
                if(sub[k]==sub[sub.length()-k-1]) count++;
            } 
            if(count==sub.length()/2) return sub;
        }
    }
}
int main(){
    string s;
    cin>>s;
    string  sub=longesPlindrome(s);
    cout<<sub;
    return 0;
} 

方法二：中心扩展算法

思想：

步骤一：中心有2种，一种是一个字母（单核），另一种是两个字母之间（双核）。也就是奇数长度子串和偶数长度子串。首先确定中心位置i（遍历所有i的情况），分单核和双核两种情况进行步骤二计算，单核：初始low =i，high=i；双核low=i,high = i+1。

步骤二：确定好中心位置后向两个方向扩展，判断low和high是否不超过原字符串的下限和上限，以及low和high处的字符是否相等，相等则low--、high++继续步骤二。否者返回right-left-1，为以该i为中心时能找到的最长回文字符串。

步骤三：判断该次以i为中心的单核、双核情况下得到的最长长度，以及变量maxLen保存的所求得的最大长度比较，将最大值赋值给maxLen变量，并且得到此时最长回文子串sub。

步骤四：遍历完所有中心i后，sub字符串为得到的最长回文子串。

时间复杂度：遍历字符：一层循环、O(n-1)；找以当前字符为中心的最长回文子串：嵌套两个独立循环、O(2n*(n-1)) = O(n^2)。

#include<iostream>
using namespace std;
int max(int a,int b){
    return a>b ? a: b;
}
int expandAroundCenter(string s,int left, int right){
        while(left>=0 && right<s.size() && s[left]==s[right]){
            --left;
            ++right;
        }
        return right-left-1;
}
string longestPalindrome(string s) {
        if(s.empty())
            return "";

        int startIndex=0;
        int maxLen=1;
        for(int i=0;i<s.size();++i){
            int len1=expandAroundCenter(s,i,i);
            int len2=expandAroundCenter(s,i,i+1);
            int len=max(len1,len2);
            if(len>maxLen){
                startIndex=i-(len-1)/2;
                maxLen=len;
            }
        }
        return s.substr(startIndex,maxLen);
    }

int main(){
    string s;
    cin>>s;
    string sub=longestPalindrome(s);
    cout<<sub;
    return 0;
}

方法三：动态规划：

i，j分别是子串的头索引和尾索引。
对于字符串str，假设dp[i,j]=1表示str[i...j]是回文子串，那个必定存在dp[i+1,j-1]=1。这样最长回文子串就能分解成一系列子问题，可以利用动态规划求解了。首先构造状态转移方程：

上面的状态转移方程表示，当str[i]=str[j]时，如果str[i+1...j-1]是回文串，则str[i...j]也是回文串；如果str[i+1...j-1]不是回文串，则str[i...j]不是回文串。
初始状态：dp[i][i]=1（单核）dp[i][i+1]=1 if str[i]==str[i+1]（双核）

时间复杂度：O(n^2)

 #include<iostream>
#include<vector>
using namespace std;
string longestPalindrome(string s)
{
    if (s.empty()) return "";
    int len = s.size();
    if (len == 1)return s;
    int longest = 1;
    int start=0;
    vector<vector<int> > dp(len,vector<int>(len));
    for (int i = 0; i < len; i++)
    {
        dp[i][i] = 1;
        if(i<len-1)
        {
            if (s[i] == s[i + 1])
            {
                dp[i][i + 1] = 1;
                start=i;
                longest=2;
            }
        }
    }
    for (int l = 3; l <= len; l++)//子串长度
    {
        for (int i = 0; i+l-1 < len; i++)//枚举子串的起始点
        {
            int j=l+i-1;//终点
            if (s[i] == s[j] && dp[i+1][j-1]==1)
            {
                dp[i][j] = 1;
                start=i;
                longest = l;
            }
        }
    }
    return s.substr(start,longest);
}
int main(){
    string s;
    cin>>s;
    string sub=longestPalindrome(s);
    cout<<sub;
    return 0;
}

方法（四）Manacher法

这是一个专门用作处理最长回文子串的方法，这里直接借用了别人的讲解方法。其实主要思想是，把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串，这个叫中心扩展法，但是这个方法还要考虑到处理abba这种偶数个字符的回文串。Manacher法将所有的字符串全部变成奇数个字符。

时间复杂度为：O(n)

#include<iostream>
#include<vector>
using namespace std;
string longestPalindrome(string s)
 {
    string manaStr = "$#";
    for (int i=0;i<s.size();i++) //首先构造出新的字符串
　　{
      manaStr += s[i];
      manaStr += '#';
    }
    vector<int> rd(manaStr.size(), 0);//用一个辅助数组来记录最大的回文串长度，注意这里记录的是新串的长度，原串的长度要减去1
    int pos = 0, mx = 0;
    int start = 0, maxLen = 0;
    for (int i = 1; i < manaStr.size(); i++) 
    {
      rd[i] = i < mx ? min(rd[2 * pos - i], mx - i) : 1;
      while (i+rd[i]<manaStr.size() && i-rd[i]>0 && manaStr[i + rd[i]] == manaStr[i - rd[i]])//这里要注意数组越界的判断，源代码没有注意，release下没有报错
          rd[i]++;
      if (i + rd[i] > mx) //如果新计算的最右侧端点大于mx,则更新pos和mx
      {
        pos = i;
        mx = i + rd[i];
      }
      if (rd[i] - 1 > maxLen)
　　　 {
        start = (i - rd[i]) / 2;
        maxLen = rd[i] - 1;
      }
    }
    return s.substr(start, maxLen);
  }
int main(){
    string s;
    cin>>s;
    string sub=longestPalindrome(s);
    cout<<sub;
    return 0;
}