傳送門

對\(A\)、\(B\)串各跑一遍\(manacher\)，求出第\(1\)、\(2\)類扭動回文串的最大長度。

考慮第三類的扭動回文串\(S(i,j,k)\)，一定可以表示為\(A(i,l)+A(l+1,j)+B(j,k)\)或\(A(i,j)+B(j,l)+B(l+1,k)\)，其中，第一段與第三段對稱（第一段正著\(Hash\)和第三段反著\(Hash\)相同），第二段是一個回文子串，三段都可以是空串。

我們可以分別在\(AB\)上枚舉對稱中心，然后感性理解一下發現肯定是取以該對稱中心為中心的最長回文串作為中間那段是最優的。然后對于第一段和第三段分別二分其長度就好了

//minamoto #include<bits/stdc++.h> #define R register #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} inline char gc(){char ch;while((ch=getc())<'A'||ch>'Z');return ch;} const int N=2e5+5,P1=1e9+7,P2=998244353; int a[N],b[N],sum[N][2],num[N][2],bin[N][2],f[N],g[N]; int n,m,ans,p,l,r;char ch; bool ck(int l1,int r1,int l2,int r2){int x,y;x=(sum[r1][0]-1ll*sum[l1-1][0]*bin[r1-l1+1][0]%P1)%P1;y=(num[l2][0]-1ll*num[r2+1][0]*bin[r2-l2+1][0]%P1)%P1;x=(x+P1)%P1,y=(y+P1)%P1;if(x!=y)return false;x=(sum[r1][1]-1ll*sum[l1-1][1]*bin[r1-l1+1][1]%P2)%P2;y=(num[l2][1]-1ll*num[r2+1][1]*bin[r2-l2+1][1]%P2)%P2;x=(x+P2)%P2,y=(y+P2)%P2;return x==y; } int calc(int j,int k){int l=0,r=min(j,n-k+1),res=0;while(l<=r){int mid=(l+r)>>1;if(ck(j-mid+1,j,k,k+mid-1))res=mid,l=mid+1;else r=mid-1;}return res; } int main(){ // freopen("testdata.in","r",stdin);scanf("%d",&n);bin[0][0]=bin[0][1]=1;fp(i,1,n)bin[i][0]=1ll*bin[i-1][0]*27%P1,bin[i][1]=1ll*bin[i-1][1]*27%P2;a[0]=b[0]=0,a[n*2+2]=b[n*2+2]=28,a[1]=b[1]=27;fp(i,1,n)ch=gc(),a[i*2]=ch-'A'+1,a[i*2+1]=27;fp(i,1,n)ch=gc(),b[i*2]=ch-'A'+1,b[i*2+1]=27;p=0;fp(i,2,n*2){if(i<=p+f[p])f[i]=min(f[2*p-i],p+f[p]-i);while(a[i-f[i]-1]==a[i+f[i]+1])++f[i];if(i+f[i]>p+f[p])p=i;}p=0;fp(i,2,n*2){if(i<=p+g[p])g[i]=min(g[2*p-i],p+g[p]-i);while(b[i-g[i]-1]==b[i+g[i]+1])++g[i];if(i+g[i]>p+g[p])p=i;}fp(i,2,n*2)cmax(ans,max(f[i],g[i]));fp(i,1,n){sum[i][0]=(1ll*sum[i-1][0]*27%P1+a[i*2])%P1;sum[i][1]=(1ll*sum[i-1][1]*27%P2+a[i*2])%P2;}fd(i,n,1){num[i][0]=(1ll*num[i+1][0]*27%P1+b[i*2])%P1;num[i][1]=(1ll*num[i+1][1]*27%P2+b[i*2])%P2;}fp(i,2,n*2){l=(i-f[i]+1)>>1,r=(i+f[i])>>1;cmax(ans,f[i]+calc(l-1,r)*2);l=(i-g[i]+1)>>1,r=(i+g[i])>>1;cmax(ans,g[i]+calc(l,r+1)*2);}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/bztMinamoto/p/10107707.html

總結

以上是生活随笔為你收集整理的P4324 [JSOI2016]扭动的回文串的全部內容，希望文章能夠幫你解決所遇到的問題。

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