今天学习了一个马拉松算法,真不戳!!!
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e7;//题目给的大小为1.1e7,我们要开的大小至少为她两倍,因为我们还要插入#号
char a[N];//上面表示初始的数组
char s[N];//下面表示插入#后的数组
int d[N];//表示相应点的回文半径的大小
void get_d(char*s,int n)
{
d[1]=1;//这里的第一个的半径肯定为1
for(int i=2,l,r=1;i<=n;i++)
{
if(i<=r)
{
d[i]=min(d[l+r-i],1+r-i);//这里是判断有没有超出边界
}
while(s[i-d[i]]==s[i+d[i]])
{
d[i]++;
}
if(i+d[i]-1>r)
{
l=i-d[i]+1;
r=i+d[i]-1;
}
}
}
int main()
{
scanf("%s",a+1);//输入原串
int n=strlen(a+1),k=0;//求出原串的长度
s[0]='$';
s[++k]='#';
for(int i=1;i<=n;i++)
s[++k]=a[i],s[++k]='#';
n=k;//将这里的k重新赋值给我们的n
get_d(s,n);
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,d[i]);
}
cout<<ans-1<<endl;
return 0;
}