题解 | #密码截取# 马拉车
密码截取
https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=11000002;
char s[N<<1];
int p[N<<1];
int main()
{
cin>>s+1;
int n=strlen(s+1);
for(int i=2*n+1;i>=1;i--){
if(i&1) s[i]='#';
else s[i]=s[i>>1];
}
s[0]='^';
s[2*n+2]='$';
int c=0,r=0;
for(int i=1;i<=2*n+1;i++){
p[i]=i<r?min(r-i,p[2*c-i]):1;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(i+p[i]>r) {
c=i;
r=i+p[i];
}
}
int ans=0;
for(int i=1;i<=2*n+1;i++){
ans=max(ans,p[i]-1);
}
cout<<ans<<'\n';
// 请在此输入您的代码
return 0;
}
查看14道真题和解析
投递拼多多等公司10个岗位 >