1
* 難度：初級(jí)
2 * 問題：從輸入文件calfflac.in中讀取文本，找到最長(zhǎng)的回文串（翻轉(zhuǎn)之后和它自己相等的字符串），只考慮字母，不區(qū)分大小寫
3 * 輸出最長(zhǎng)回文串的長(zhǎng)度，并且輸出它在原文中的對(duì)應(yīng)的串。如果多個(gè)回文串長(zhǎng)度相等，輸出第一個(gè)。
4 * 注：該題目來自：http://ace.delos.com/usacogate，有興趣的朋友可以去上面注冊(cè)，很好的練習(xí)平臺(tái)。
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;//回文串的長(zhǎng)度
35 int maxIndex=0;//回文串的中間字母的索引
36 len=letters.length();
37 for(int i=0;i<len;i++)//挨個(gè)試
38 {
39 int length=maxLength+1;//找下一個(gè)更長(zhǎng)的，因?yàn)轭}目要求，如果是同樣長(zhǎng)度的，只輸出最前面的那個(gè)。
40 boolean isChanged=false;//回文串的長(zhǎng)度可以是奇數(shù)個(gè)，也可以是偶數(shù)個(gè)，這個(gè)用于切換
41 for(;i-(length-1)/2>=0&&i+length/2<len;)
42 {
43 //通過當(dāng)前的i(回文串的中間)，以及長(zhǎng)度，找到待測(cè)定的一段字符串并測(cè)試
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++;//奇數(shù)個(gè)和偶數(shù)個(gè)切換
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(luò)(都包含在內(nèi))之間的字符串是否回文。
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