1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
int n;
string ps;
int d[60000001];
char s[60000001];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>ps;
n=ps.length()*2+1;
s[1]='#';
for(int i=2;i<=n;i+=2)
{
s[i]=ps[i/2-1];
s[i+1]='#';
}
int l=0,r=-1;
for(int i=1;i<=n;i++)
{
if(i<=r)
{
d[i]=min(d[l+r-i],r-i+1);
}
else
{
d[i]=1;
}
while(i-d[i]>0&&i+d[i]<=n&&s[i+d[i]]==s[i-d[i]])
{
d[i]++;
}
if(i+d[i]-1>r)
{
r=i+d[i]-1;
l=i-d[i]+1;
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,d[i]-1);
}
cout<<ans<<endl;
return 0;
}
|