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
