题目链接:http://pat.zju.edu.cn/contests/pat-a-practise/1040
采用两次遍历,第一次以所在元素为中心,向外侧求offset,并记录最大值。第二次以元素与下一个元素中间为中心,向外扩展求offset,并与之前最大值比较。
暴力
// 暴力破解 // 分类讨论 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> #include <math.h> #include <iostream> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <algorithm> #define SIZE 1000+10 using namespace std; char buf[SIZE]; int F[SIZE]; int n; void Init() { memset(buf, 0, sizeof(buf)); } void InitF() { int i; for(i=0; i<n; i++) { F[i]=1; } } int form1(int i) { int j, k; int len=1; j=i-1; k=i+1; while(j>=0 && k<n) { if(buf[j] == buf[k]) { len += 2; } else { break; } j--; k++; } return len; } int form2(int i) { int j, k; int len=0; j=i; k=i+1; while(j>=0 && k<n) { if(buf[j] == buf[k]) { len += 2; } else { break; } j--; k++; } return len; } int main() { #ifdef ONLINE_JUDGE #else freopen("E:\\in.txt", "r", stdin); #endif Init(); gets(buf); n=strlen(buf); InitF(); // 特例 if(n == 2) { if(buf[0] == buf[1]) { F[0]=2; } } //3个元素以上 int i, max=-1; for(i=0; i<n; i++) { int max1 = form1(i); int max2 = form2(i); F[i] = max1>max2 ? max1:max2; if(max < F[i]) { max = F[i]; } } printf("%d\n", max); return 0; }
改变存储