//译题 //★Calf Flac 最长的回文 据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最 棒的回文. 你的工作就是去这些牛制造的奇观中寻找最长的回文. 寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母 'A'-'Z'和'a'-'z'. 要你寻找的最长的回文的文章是一个不超过20,000 个字符的字符串. 我们将保证最长的回文不会超过2,000 个字符(在除去标点符号、空格之前). PROGRAM NAME: calfflac INPUT FORMAT 一个不超过20,000 个字符的文件. SAMPLE INPUT (file calfflac.in) Confucius say: Madam, I'm Adam. OUTPUT FORMAT 输出的第一行应该包括找到的最长的回文的长度. 下一个行或几行应该包括这个回文的原文(没有除去标点符号、空格), 把这个回文输出到一行或多行(如果回文中包括换行符). 如果有多个回文长度都等于最大值,输出那个前出现的. SAMPLE OUTPUT (file calfflac.out) 11 Madam, I'm Adam
/* 枚举中间数 （也就是认为它是回文数最中间的字母）， 然后左右扩展（忽略非字母）至出界和不相等。 最后更新最大值。要考虑回文是奇数和偶数两种情况。 提示大家在开始扩展之前就判断 （很巧妙，大家举几个例子就可以明白了）。 输入中的换行符可以维持原样不变，PASCAL不会输出成乱码。 另一种O(n)的动态规划算法。 方程f[i]=f[i-1]+2 如果(a[i]=a[i-f[i-1]-1]) 或 f[i]=2 如果(a[i]=a[i-1]) 或 f[i]=1 其中f[i]是以恰好第i个字符结尾的回文串最大长度。速度巨快如雷电.. 我只写了一种,代码有点长，动态规划的那个还没搞懂 */ --------------------------------------------------------------------------------------------------- 参考代码（代码中附有解释） --------------------------------------------------------------------------------------------------- #include<stdio.h> #include<string.h> int min(int a, int b) { return a<b?a:b; } char s_old[20000], s_new[20000]; //s_old存放原字符串，s_new存放新字符串 int pos[20000]={0}; //pos数组存放新数组中的字符在原数组中的位置 int main() { freopen("calfflac.in","r",stdin); freopen("calfflac.out","w",stdout); int i,j,k； int len1=0,len2=0,max1=0,max2=0,tmp1=0,tmp2=0; while(scanf("%c",&s_old[len1++])!=EOF); len1--; //len 为旧数组的长度 for(i=0;i<len1;i++) //将s_old转化为s_new，转化的同时将字母的大小写统一为大写 { if( (s_old[i]>='A' && s_old[i]<='Z' )||(s_old[i]>='a' && s_old[i]<='z' )) { if((s_old[i]>='a' && s_old[i]<='z' )) s_new[len2++] = s_old[i] - 'a' + 'A'; else s_new[len2++] = s_old[i]; pos[len2-1] = i; } } for(i=1;i<len2;i++) //假设最大回文数是奇数，找到这个最大回文数 { //同时用tmp确定位置 j=0; //用到的算法在前面 讲过了 while(s_new[i-j] == s_new[i+j] && j<=i && i+j<len2) { if(max1 < 2*j+1) { max1=2*j+1; tmp1 = i-j; } j++; } } for(i=1;i<len2;i++) //假设最大回文数为偶数，找到这个最大回文数 { j=0; while(s_new[i-j-1] == s_new[i+j] && j<=i && i+j<len2) { if(max2 < 2*j) { max2=2*(j+1); tmp2 = i-j-1; } j++; } } if(max1==max2) tmp1=min(tmp1,tmp2); else if(max1 < max2) { max1=max2; tmp1=tmp2; } printf("%d ", max1); for(i=pos[tmp1];i<=pos[tmp1+max1-1];i++) //按照原位置输出字符串 printf("%c",s_old[i]); printf(" "); return 0; } /* for(i=0; i < len2; i++) 这也是一种想法 for(j=i; j < len2; j++) { int ok =1; for(k=i;k<=j;k++) if(s_new[k] != s_new[i+j-k]) ok = 0; if(ok && j-i+1 > max) {max = j - i + 1; tmp = i;} } */