Java实现从文本中查找最长的回文字符串[Java编程]

1　*　难度:初级
2　*　问题:从输入文件calfflac.in中读取文本,找到最长的回文串（翻转之后和它自己相等的字符串）,只考虑字母,不辨别大小写
3　*　输出最长回文串的长度,并且输出它在原文中的对应的串.假如多个回文串长度相等,输出第一个.
4　*　注:该标题来自:http://ace.delos.com/usacogate,有爱好的朋友可以去上面注册,很好的操练平台.
5*/
6import　java.util.*;
7import　java.io.*;
8class　calfflac
9{
10　　public　static　void　main　(String　[]　args)　throws　IOException　{
11　　　　//　Use　BufferedReader　rather　than　RandomAccessFile;　it's　much　faster
12　　　　　BufferedReader　f　=　new　BufferedReader(new　FileReader("calfflac.in"));
13　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//　input　file　name　goes　above
14　　　　　　　　PrintWriter　out　=　new　PrintWriter(new　BufferedWriter(new　FileWriter("calfflac.out")));
15　　　　String　temp=null;
16　　　　StringBuilder　origin=new　StringBuilder(20000);//包含本来的字符串
17　　　　StringBuilder　letters=new　StringBuilder(20000);//包含字母
18　　　　int[]　indexes=new　int[20000];
19　　　　while((temp=f.readLine())!=null)
20　　　　{
21　　　　　　　　origin.append(temp);
22　　　　　　　　origin.append('\n');
23　　　　}
24　　　　int　len=origin.length();
25　　　　for(int　i=0;i<len;i++)
26　　　　{
27　　　　　　　　char　c=(origin.charAt(i));
28　　　　　　　　if(c>='a'&&c<='z'||c>='A'&&c<='Z')//只要字母
29　　　　　　　　{
30　　　　　　　　　　　　letters.append(origin.charAt(i));
31　　　　　　　　　　　　indexes[letters.length()-1]=i;
32　　　　　　　　}
33　　　　}
34　　　　int　maxLength=1;//回文串的长度
35　　　　int　maxIndex=0;//回文串的中间字母的索引
36　　　　len=letters.length();
37　　　　for(int　i=0;i<len;i++)//挨个试
38　　　　{
39　　　　　　　　int　length=maxLength+1;//找下一个更长的,因为标题要求,假如是一样长度的,只输出最前面的那个.
40　　　　　　　　boolean　isChanged=false;//回文串的长度可以是奇数个,也可以是偶数个,这个用于切换
41　　　　　　　　for(;i-(length-1)/2>=0&&i+length/2<len;)
42　　　　　　　　{
43　　　　　　　　　　　　//通过当前的i(回文串的中间),以及长度,找到待测定的一段字符串并测试
44　　　　　　　　　　　　if(ispal(letters,i-(length-1)/2,i+length/2))
45　　　　　　　　　　　　{
46　　　　　　　　　　　　　　　　maxLength=length;
47　　　　　　　　　　　　　　　　maxIndex=i;
48　　　　　　　　　　　　　　　　length+=2;
49　　　　　　　　　　　　}
50　　　　　　　　　　　　else　if(!isChanged)//切换
51　　　　　　　　　　　　{
52　　　　　　　　　　　　　　　　isChanged=true;
53　　　　　　　　　　　　　　　　length++;//奇数个和偶数个切换
54　　　　　　　　　　　　}
55　　　　　　　　　　　　else
56　　　　　　　　　　　　　　　　break;
57　　　　　　　　}
58　　　　}
59　　　　//背面的代码,将找出回文串在原字符串中的模样.
60　　　　int　start=indexes[maxIndex-(maxLength-1)/2];
61　　　　int　end=indexes[maxIndex+(maxLength)/2];
62　　　　String　result=origin.substring(start,end+1);
63　　　　out.println(maxLength);
64　　　　out.println(result);
65　　　　out.flush();
66　　　　out.close();
67　　　　System.exit(0);
68　　}
69　　//判断s中i到j(都包含在内)之间的字符串能否回文.
70　　static　boolean　ispal(StringBuilder　s,int　i,int　j)
71　　{
72　　　　　　char　c1='0',c2='0';
73　　　　　　for(;i<j;i++,j--)
74　　　　　　{
75　　　　　　　　c1=s.charAt(i);
76　　　　　　　　c2=s.charAt(j);
77　　　　　　　　if(c1!=c2&&(c1-c2)%32!=0)
78　　　　　　　　return　false;
79　　　　　　}
80　　　　　　return　true;
81　　}
82}
83