傳送門

#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 300 #define mod 1000000007 using namespace std; int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } const int N=1e6+10; char s[N],str[N*4]; int p[N*4],len1,len2; void init() {len1=strlen(s);str[0]='(';str[1]='#';for(int i=0;i<len1;i++){str[i*2+2]=s[i];str[i*2+3]='#';}len2=len1*2+2;str[len2]=')'; } void Manacher() {memset(p,0,sizeof(p));int id=0,mx=0;for(int i=1;i<len2;i++){if(mx>i) p[i]=min(mx-i,p[2*id-i]);else p[i]=1;for(;str[i+p[i]]==str[i-p[i]];p[i]++);if(p[i]+i>mx){mx=p[i]+i;id=i;}} } int main() {int T=read();while(T--){scanf("%s",s);init();Manacher();int mx=1;for(int i=0; i<len2; i++) mx=max(mx,p[i]);printf("%d\n",mx-1);}return 0; }

點擊回到頂部

轉載于:https://www.cnblogs.com/zsyacm666666/p/6740700.html

總結

以上是生活随笔為你收集整理的hihocoder 1032 最长回文子串(Manacher)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。