PTA1040 Longest Symmetric String（回文串,dp）

分析：直接暴力时间复杂度大概是o(n^3).
如果采用dp，时间复杂度大概是o(n^2).
曼彻斯特解法可以降到o(n)

下面给出dp解法：
$dp[i][j]$表示s[i]到s[j]部分的字符串是否是回文串，如果是则为1，如果不是则为0.

#include<iostream>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
string s;
int dp[1100][1100],ans;
int main(){
    std::ios::sync_with_stdio(false);memset(dp,0,sizeof(dp));getline(cin,s);int len=s.length();ans=1;//dp[i][j]表示以i和j为端点是否是回文，是1，非0for(int i=0;i<len;i++){
    dp[i][i]=1;if(s[i]==s[i+1]&&i+1<len){
    dp[i][i+1]=1;ans=2;}}//枚举字符串的长度for(int L=3;L<=len;L++){
    //枚举左右端点for(int i=0;i+L-1<len;i++){
    int j=i+L-1;if(s[i]==s[j]&&dp[i+1][j-1]==1) {
    dp[i][j]=1; ans=L;}    //更新最大的长度//else {dp[i][j]=0;}}}cout<<ans<<endl;return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
string s;
int maxx=1;
void judge(int ll,int rr){
    bool flag=true;for(int i=ll,j=rr;i<=rr,j>=ll;i++,j--){
    if(s[i]!=s[j]){
    flag=false;break;}if(i>j){
    break;}}if(flag){
    maxx=max(maxx,rr-ll+1);}return ;
}
int main(){
    std::ios::sync_with_stdio(false);//最长回文串getline(cin,s);int len=(int)s.length();for(int i=0;i<len;i++){
    for(int j=i+1;j<len;j++){
    judge(i,j);}}cout<<maxx<<endl;return 0;
}