天梯赛L2-008. 最长对称子串（ manacher算法）

L2-008. 最长对称子串

时间限制

100 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定"Is PAT&TAP symmetric?"，最长对称子串为"s PAT&TAP s"，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<set>
 7 
 8 using namespace std;
 9 
10 string temp,s;
11 int p[2005];
12 
13 void solve()
14 {
15     int id=0,maxid=0;
16     unsigned long int len = s.length();
17     for(int i = 0; i < len; i++)
18     {
19         if(i<maxid)
20             p[i]=min(p[2*id-i],maxid-i);
21         else
22             p[i]=1;
23         while(s[i+p[i]]==s[i-p[i]])
24             p[i]++;
25         if(p[i]+i>maxid)
26             maxid=p[i]+i,id=i;
27     }
28 }
29 int main()
30 {
31     memset(p,0,sizeof(p));
32     getline(cin,temp);
33     unsigned long int len = temp.length();
34     s="$#";
35     for(int i = 0; i < len;i++)
36     {
37         s+=temp[i];
38         s+="#";
39     }
40     s+="";
41     solve();
42     int max=0;
43     len = s.length();   //忘记写这句，过一半的样例，恐怖的代码习惯
44     for(int i = 0; i < len; i++)
45         if(p[i]>max)
46             max=p[i];
47     cout<<max-1<<endl;
48     
49 }