USACO 1.3.3 最长的回文 （Calf Flac）Java实现

据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最 棒的回文. 你的工作就是去这些牛制造的奇观中寻找最长的回文. 寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母 ‘A’-‘Z’和’a’-‘z’. 要你寻找的最长的回文的文章是一个不超过 20,000 个字符的字符串. 我们将保证最长的回文不会超过 2,000 个字符(在除去标点符号、空格之前).

输入格式:

一个不超过 20,000 个字符的文件.

输出格式:

输出的第一行应该包括找到的最长的回文的长度. 下一个行或几行应该包括这个回文的原文(没有除去标点符号、空格), 把这个回文输出到一行或多行(如果回文中包括换行符). 如果有多个回文长度都等于最大值,输出那个前出现的.

输入样例:

在这里给出一组输入。例如：

Confucius say: Madam, I’m Adam.

输出样例:

在这里给出相应的输出。例如：

11 Madam, I’m Adam

代码如下：

import java.util.Scanner; public class Main { static char s[]=new char[40005],t[]=new char[40005]; static int a[]= new int[40005]; static int cnt=0; static int cntt=0; public static int huiwen(int x){//从下标x向两侧延伸 int ans1=1,ans2=0; for(int j=1;j<=x&&j+x<cnt&&t[x-j]==t[x+j];j++) ans1+=2;//奇数延拓 for(int i=x,j=x+1;i>=0&&j<cnt&&t[i]==t[j];i--,j++) ans2+=2;//偶数延拓 return Math.max(ans1,ans2); } public static void main(String[] args){ Scanner in=new Scanner(System.in); int maxm=0,maxx=0; String str=new String(); while(in.hasNext()) { str=str+in.nextLine()+'\n';//因为有的字符串不满一行就可能换行，所以我们每次加‘\n’ 自己测试代码的时候按Ctrl+z结束输入 } str=str.substring(0,str.length()-1);//去掉最后的一个换行 s=str.toCharArray(); cntt=str.length(); for(int i=0;i<cntt;i++){ if(s[i]>='A'&&s[i]<='Z'){ a[cnt]=i; t[cnt++]= (char) (s[i]-'A'+'a'); } else if(s[i]>='a'&&s[i]<='z'){ a[cnt]=i; t[cnt++]=s[i]; } } t[cnt]='\0'; for(int i=0;i<cnt;i++){ int lenoi=huiwen(i); if(lenoi>maxm){ maxm=lenoi; maxx=i; } } System.out.println(maxm); if(maxm%2>0){ int begin=maxx-maxm/2; int end=maxx+maxm/2; for(int i=a[begin];i<=a[end];i++){ System.out.print(s[i]); } } else{ int begin=maxx-maxm/2+1; int end=maxx+maxm/2; for(int i=a[begin];i<=a[end];i++){ System.out.print(s[i]); } } } }