题解 | #最长回文子串#

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int getLongestPalindrome (string s)
{   


    int length =0;
    int n =s.size();
    //space:
    vector<vector<bool>> dp(n,vector<bool>(n,false));

    for( int end  =0;end <n;end++)
    {
        for( int start =0; start <=end;start++)
        {
            if (s[start] == s[end])
            {    
                if (end -start <2 )
                {
                     // 每个子串 100%是回文。[a] [aa] [aba]
                     dp[start][end] =true;
                }else
                {
                     dp[start][end] =  dp[start+1][end-1]; 
                }

                //双指针 end-1 >=start+1  end -start >=2

            }else
            {
                dp[start][end] = false; //[a?b]
            }

            if ( true == dp[start][end]  && end -start +1 > length)
            {
                length = end -start +1;
            }
        }
    }

    return length;

}


int main()
{
  string s;
  while(cin>>s)
  {
      cout << getLongestPalindrome(s)<<endl;
  }
}