题解 | #最长回文子串#
最长回文子串
http://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507
#include <bits/stdc++.h>
using namespace std;
bool dp[355][355];//dp[i][j]表示区间[i,j]是否为回文子串
int main(){
string s;
while(cin>>s){
for(int i=0;i<s.length();i++)
dp[i][i]=true;
for(int i=0;i<s.length()-1;i++)
dp[i][i+1]=(s[i]==s[i+1]);
for(int len=3;len<=s.length();len++){//由于在计算时是通过短的子串来获得大的子串的,所以不能直接枚举i,j,必须按照长度从小到大枚举
for(int i=0;i<s.length()-len+1;i++){
int l=i,r=i+len-1;
dp[l][r]=dp[l+1][r-1]&(s[l]==s[r]);
}
}
int maxx=1;
for(int i=0;i<s.length();i++)
for(int j=i + 1;j<s.length();j++)
if(dp[i][j])
maxx=max(maxx,j-i+1);
cout<<maxx<<endl;
}
}