截图来自董老师https://www.bilibili.com/video/BV173411V7Ai/?spm_id_from=333.999.0.0&vd_source=23dc8e19d485a6ac47f03f6520fb15c2
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<cstdio> #include<queue> #include<map> #include<vector> #include<set> using namespace std; const int maxn=3e7+10; const int INF=0x3fffffff; typedef long long LL; char a[maxn],s[maxn]; int d[maxn]; void get_d(char *s,int n){ d[1]=1; for(int i=2,l,r=1;i<=n;i++){ if(i<=r) d[i]=min(d[r-i+l],r-i+1); 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); int k=0; s[0]='$'; s[++k]='#'; for(int i=1;i<=n;i++){ s[++k]=a[i];s[++k]='#'; } n=k; get_d(s,n); int ans=0; for(int i=1;i<=n;i++) ans=max(ans,d[i]); printf("%d",ans-1); return 0; }
标签:const,int,char,算法,maxn,include,拉车 From: https://www.cnblogs.com/shirlybaby/p/17478908.html