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