这个题目对我而言的意义就是让我熟悉了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表示该处字符在原串中的位置,这样记录后输出就比较方便.