文本中找最长的回文字符串

核心提示：1*难度：初级2*问题：从输入文件calfflac.in中读取文本，找到最长的回文串（翻转之后和它自己相等的字符串），文本中找最长的回文字符串，只考虑字母，不区分大小写3*输出最长回文串的长度，找到待测定的一段字符串并测试44if(ispal(letters,i-(length-1)/2,i+length/2))45{

　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