马拉车算法,我调了两天了,还是只得20分,到底为什么啊我快疯了o(╥﹏╥)o
#include<bits/stdc++.h>
using namespace std;
char s[30000000];
int l=2,p[30000000],maxn=1;
void _int()
{
s[0]='$';s[1]='#';
char x;
x=getchar();
while(x>='a'&&x<='x')
{
s[l++]=x;
s[l++]='#';
x=getchar();
}
s[l]='^';
return;
}
int main()
{
_int();
int mid,r=1;
for(int i=1;i<l;i++)
{
if(i<r)
p[i]=min(p[mid-(i-mid)],r-i);
else
p[i]=1;
while(s[i+p[i]]==s[i-p[i]])
p[i]++;
if(r<i+p[i])
{
mid=i;
r=i+p[i];
}
maxn=max(maxn,p[i]-1);
}
cout<<maxn<<endl;
return 0;
}