這個題目對我而言的意義就是讓我熟悉了while (cin.get(ch))這樣的寫法.
之前深入思考過這個題目,甚至想要像KMP算法那樣構造出一些函數
來降低復雜度.不過沒能想出更好的辦法,最后還是選擇了以前的老辦
法:枚舉中點.
為了省事,我直接拷貝了一份字符串,而把原來的字符串作為bak儲存.
下面是代碼:
1 /*
2 ID:31440461
3 PROG:calfflac
4 LANG:C++
5 */
6 #include<iostream>
7 #include<string>
8 using namespace std;
9 const int MAXL=2000000+10;
10 int b,e,mlen=0;
11 char bak[MAXL];
12 struct re
13 {
14 char ch;
15 int pos;
16 }
17 text[MAXL/10];
18
19 int main()
20 {
21 freopen("calfflac.in","r",stdin);
22 freopen("calfflac.out","w",stdout);
23 int len=-1;
24 char ch;
25 while(cin.get(ch)) bak[++len]=ch;
26 int l=-1;
27 for (int i=0;i<=len ;i++ )
28 if (isalpha(bak[i]))
29 {
30 text[++l].ch=toupper(bak[i]);
31 text[l].pos=i;
32 }
33
34 /* 以i為中點,往兩頭匹配 */
35 for (int i=0;i<=l ;i++ )
36 {
37 int d=1;
38 while((i-d>=0)&&(i+d<=l)&&(text[i-d].ch==text[i+d].ch)) ++d;
39 --d;
40 if (d*2+1>mlen)
41 {
42 mlen=d*2+1;
43 b=text[i-d].pos;
44 e=text[i+d].pos;
45 }
46 }
47
48 /* 以i,i+1為中間兩點,向兩邊匹配 */
49 for (int i=0;i<l;i++ )
50 {
51 int d=0;
52 while ((i-d>=0)&&(i+1+d<=l)&&(text[i-d].ch==text[i+1+d].ch)) ++d;
53 --d;
54 if (d*2+2>mlen)
55 {
56 mlen=d*2+2;
57 b=text[i-d].pos;
58 e=text[i+1+d].pos;
59 }
60 }
61 /* 輸出 */
62 cout << mlen << endl;
63 for (int i=b;i<=e ;i++ ) cout << bak[i];
64 cout << endl;
65 return 0;
66 }
67
text的一個參數pos表示該處字符在原串中的位置,這樣記錄后輸出就比較方便.