题目大意:输入最长两万个字符,判断最长的英文字母回文子串,输出长度和子串。
其实是挺简单的字符串题,方法是枚举每一位是子串的中间值,有字串长度奇数、偶数两种情况,分别考虑。但是字符串题很麻烦,尤其这道题是多行输入,我最开始用gets输入,但是最后结果没有换行符,我又再每次读完一行后在最后一个字符处加换行符,可是这样有一组样例最大字串的中间值是回车,导致总长度多了1。最后新设了一个标记数组,记录第几位有回车,输出按照输出字符的方式,到了特定位置如果有回车就输出回车,最后再输出一个回车。这样导致的结果是有可能最后一个字符后面有回车,判断输出了,结束又一个回车,就多输出了一个回车,又WA了一发,总共WA了5发以上,实在不够机智。
/* ID: zz401 LANG: C++ TASK: calfflac */ #include<cstring> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cmath> #include<cctype> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #define PI acos(-1.0) using namespace std; char a[20005]; int bn[20005]={0}; int sum,p,q,ls,rs,l,maxm,maxml,maxmr; void solve(int i){ p = ls = i - 1; q = rs = i + 1; sum = 1; while(1){ while(ls>=0&&!isalpha(a[ls])) ls--; if(ls<0) break; while(rs<l&&!isalpha(a[rs])) rs++; if(rs>=l) break; if(toupper(a[ls])==toupper(a[rs])){ sum+=2; p = ls; q = rs; } else break; ls--; rs++; } if(sum>maxm){ maxm = sum; maxml = p; maxmr = q; } } void solve2(int i1,int i2){ p = ls = i1 - 1; q = rs = i2 + 1; sum = 2; while(1){ while(ls>=0&&!isalpha(a[ls])) ls--; if(ls<0) break; while(rs<l&&!isalpha(a[rs])) rs++; if(rs>=l) break; if(toupper(a[ls])==toupper(a[rs])){ sum+=2; p = ls; q = rs; } else break; ls--; rs++; } if(sum>maxm){ maxm = sum; maxml = p; maxmr = q; } } int main(){ freopen ("calfflac.in", "r", stdin); freopen ("calfflac.out", "w", stdout); int i; l = 0; maxm = maxml = maxmr = 1; while(gets(a+l)){ l = strlen(a); bn[l-1] = 1; } for(i=0;i<l;i++){ solve(i); if(i-1>=0&&toupper(a[i])==toupper(a[i-1])) solve2(i-1,i); if(i+1<l&&toupper(a[i+1]==toupper(a[i]))) solve2(i,i+1); } printf("%d\n",maxm); for(i=maxml;i<=maxmr;i++){ printf("%c",a[i]); if(bn[i]==1) printf("\n"); } if(bn[i-1]!=1) printf("\n"); return 0; }