最长对称子串

 1 //暴力 
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 string s,s1,s2;
 5 int l1;
 6 int main()
 7 {
 8     //数据量不大，可以2重循环 
 9     getline(cin,s);//不要用cin,cin遇到空格结束 
10     int max  = 0,l=s.size();
11     for(int i=0;i<l;i++){
12         for(int j =1;j<=l-i;j++){
13             s1=s.substr(i,j);//实际从1-i+1=i开始的 
14             //s(i,j) 就是s.substr(i,j-i+1) 
15             s2=s1;
16             reverse(s2.begin(),s2.end());
17             l1=s2.size();
18             if(s1==s2&&max<l1){//暴力判断即可 
19                 max=l1;
20             }
21         }
22     }
23     printf("%d\n",max);
24     return 0;
25     
26  } 
27 //动态规划 
28 #include<bits/stdc++.h>
29 using namespace std;
30 const int N = 1200;
31 int dp[N][N];
32 bool dp_[N][N];
33 string s;
34 int l ;
35 int main()
36 {
37     memset(dp,0,sizeof(dp));
38     memset(dp_,false,sizeof(dp_));
39     getline(cin,s);
40     l =s.size();
41 //    dp_[i][j]:从i到j是否为对称子串 
42 //    dp[i][j]:子串(i,j)范围内的最长对称子串的长度 
43     for(int i =0;i<N;i++){
44         dp[i][i]=1;
45         dp_[i][i] = true;
46     }
47     for(int j =1;j<l;j++){
48         for(int i=j-1;i>=0;i--){
49             if(s[i]==s[j]&&i+1==j){//如aa 
50                 dp_[i+1][j-1]=true;//为了下面的if,此时的i+1>j-1的 
51                 dp_[i][j]=true;
52             }
53             if(s[i]==s[j]&&dp_[i+1][j-1]){
54                 dp_[i][j] = true;
55                 dp[i][j] = dp[i+1][j-1]+2;
56             }
57             else{
58                 dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
59             }
60         }
61     }
62     printf("%d\n",dp[0][l-1]); 
63     return 0;
64  }