最大回文串 Longest Palindromic Substring

id5. Longest Palindromic Substring QuestionEditorial Solution My Submissions
Total Accepted: 147621
Total Submissions: 614546
Difficulty: Medium
Contributors: Admin
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:
Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.
Example:

Input: “cbbd”

Output: “bb”
最长回文串,首先最容易想到的是穷举所有的字串，然后判断是不是回文。
最开始的方法使用递归判断是不是回文：

//这是一种超时但是正确的做法。但是超时了。。
#include<iostream>
#include<string>
using namespace std;
bool isPalindromic(string s,int i,int j)
{
    if (i==j)
    return 1;
    if(s[i]!=s[j])
    return 0;
    if (i+1==j)
    return 1;
    return isPalindromic(s,i+1,j-1);
}
    string longestPalindrome(string s) {
        string longestPalindromeString =s.substr(0,1);
        string str;
        for(int i=0;i!=s.size();i++)
        {
            for(int j=i;j!=s.size();j++)
            {
                str=s.substr(i,j-i+1);
             if(isPalindromic(str,0,str.size()-1)&&(str.size()>longestPalindromeString.size()))
             longestPalindromeString=str;
            }
        }
        return longestPalindromeString;
    }

int main()
{ string s="sdgdfhfgjhgghkjhljkldyhrtiiiiytrewqtyitutyiyopuip";
cout<<longestPalindrome(s);
  return 0;
}

总结上面的做法，时间复杂度为 $o\left( n^2\log ^n \right) $
会发现做了很多重复的事情所以时间复杂度非常高，所以将思路变成穷举中心点，从中心按照奇数和偶数进行扩散，进而在扩散的过程就完成了回文的判断。节省了判断回文的时间。

class Solution {
public:
    string longestPalindrome(string s) {
        string longestPalindromeString =s.substr(0,1);
        for(int i=0;i!=s.size();i++)
        {   //奇数
            for(int j=0;((i-j)>=0)&&((i+j)<=s.size()-1);j++)
            {if(s[i-j]!=s[i+j])
             break;
             if ((2*j+1)>longestPalindromeString.size())
             longestPalindromeString=s.substr(i-j,2*j+1);
             }
             //偶数
            for(int j=0;((i-j)>=0)&&((i+j+1)<=s.size()-1);j++)
            { if(s[i-j]!=s[i+j+1])
             break;
             if ((2*j+2)>longestPalindromeString.size())
             longestPalindromeString=s.substr(i-j,2*j+2);
            }
        }
        return longestPalindromeString;
    }
};

这样的时间复杂度就为 $o\left( n^2 \right) $
顺别说一点，在写类的时候不要忘了在类后面加 ;号，不然会提示

error: expected unqualified-id before string constant