#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<
set>
#include<cstring>
#include<stdio.h>
using namespace std;
char ch[
5000];
int len;
/* 把第三个的判断方法和第二个的暴力方法结合在了一起，通过了*/
int test(
int i,
int flag) {
int temp = -
1, j, ans=-
1e9;
if(flag ==
1) {
temp =
1;
j =
1;
while((i-j>=
0) && (i+j<len) && (ch[i-j] == ch[i+
j])) {
j++
;
temp +=
2;
}
return temp;
}else {
if(ch[i-
1] ==
ch[i]) {
temp =
0;
j =
1;
while((i-j>=
0) && (i+j-
1<len) && (ch[i-j] == ch[i+j-
1])) {
j++
;
temp +=
2;
}
ans =
temp;
}else if(ch[i+
1] ==
ch[i]) {
temp =
0;
j =
1;
while((i-j+
1>=
0) && (i+j<len) && (ch[i-j+
1] == ch[i+
j])) {
j++
;
temp +=
2;
}
ans =
max(temp,ans);
}
return ans;
}
}
int main() {
//FILE *fp = fopen("1.txt","r");
fgets(ch,
2000, stdin);
len = strlen(ch)-
1;
int cur =
0, ans =
1;
for(
int i =
0; i < len; i++
) {
cur = max(test(i,
0),test(i,
1));
ans =
max(cur, ans);
}
cout <<
ans;
}
/* 第二个想的暴力解决方法，但是有两个测试点过不去，不知道什么地方错了。。
int main() {
//FILE *fp = fopen("1.txt","r");
fgets(ch, 2000, stdin);
len = strlen(ch)-1;
int cur = 0, ans = 1;
for(int i = 0; i < len-1; i++) {
for(int j = i+1; j < len; j++) {
cur = 0;
for(int k = i, l = 0; k <= j; k++, l++) {
int rt = j-l, lt = i+l;
if(rt == lt) {
cur += 1;
break;
} //因为是从两头开始比较，假如中间有不相等的，且遍历之后两端没连起来，就会出现错误，因此最好使用长度枚举。
if(rt < lt ) break; else if (ch[rt] != ch[lt]) { cur = 0; break; }
if(rt < lt || ch[rt] != ch[lt]) break;
cur += 2;
}
ans = max(ans,cur);
}
}
cout << ans;
}
*/
/*最初想到的办法，分治，我觉得算法复杂度应该是nlgn，但实际运行起来很慢
int test(int i, int flag) {
int temp = -1, j, ans=-1e9;
if(flag == 1) {
temp = 1;
j = 1;
while((i-j>=0) && (i+j<len) && (ch[i-j] == ch[i+j])) {
j++;
temp += 2;
}
return temp;
}else {
if(ch[i-1] == ch[i]) {
temp = 0;
j = 1;
while((i-j>=0) && (i+j-1<len) && (ch[i-j] == ch[i+j-1])) {
j++;
temp += 2;
}
ans = temp;
}else if(ch[i+1] == ch[i]) {
temp = 0;
j = 1;
while((i-j+1>=0) && (i+j<len) && (ch[i-j+1] == ch[i+j])) {
j++;
temp += 2;
}
ans = max(temp,ans);
}
return ans;
}
}
int traverse(int i, int j) {
if(i < 0 || j < 0) return 0;
if(i > j) return 0;
if(i == j) return 1;
int mid = (i+j)/2;
int ans = max(traverse(i,mid), traverse(i+1,j));
int p = max(test(mid,0),test(mid,1));
return max(ans,p);
}
int main() {
FILE *fp = fopen("1.txt","r");
fgets(ch, 2000, fp);
len = strlen(ch) ;
cout << traverse(0, len-1);
}
*/
转载于:https://www.cnblogs.com/dcklm/p/10349792.html
