51nod1088(最长回文子串)

题目链接: https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1088

题意: 中文题目诶~

思路: 这道题字符串长度限定为1e3, 所以O(n^2)也能过啦~

那么我们直接枚举所有中间位置的字符,然后取得最大值就好了啦;

注意将子串长度分下奇偶.

代码:

 1 #include <bits/stdc++.h>
 2 #define MAXN 1010
 3 using namespace std;
 4 
 5 int main(void){
 6     char ch[MAXN];
 7     int m=0, l;
 8     scanf("%s", ch);
 9     l=strlen(ch);
10     for(int i=0; i<l; i++){ //i表中间子串的中间位置
11         for(int j=0; i-j>=0&&j+i<l; j++){ //子串长度为奇数的情况, j表对称位置的长度
12             if(ch[i-j]!=ch[i+j]){
13                 break;
14             }else{
15                 m=max(m, 2*j+1);
16             }
17         }
18         for(int j=0; i-j>=0&&i+j+1<l; j++){ //子串长度为偶数的情况, j表左边中间位置到开始位置的长度
19             if(ch[i-j]!=ch[i+j+1]){
20                 break;
21             }else{
22                 m=max(m, 2*j+2);
23             }
24         }
25     }
26     printf("%d
", m);
27     return 0;
28 }