题目
非常板子了
看到求什么最长的回文，我们就想到枚举回文中心的方法
首先对于这个回文串只包含在一个串内的情况，我们随便一搞就可以了，大概\(Manacher\)一下就没有了
对于那种扭动的回文串，我们枚举回文中心，求一下回文半径，我们发现其必须先在一个串内扩展一个最长回文半径的长度，再去另外一个串扩展才是最优的
于是我们对这个两个串正反建\(SA\)求一下\(lcp\)就没了
代码
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))const int maxn=4e5+10;char A[100005],B[100005],S[maxn];int sa[maxn],rk[maxn],tax[maxn],tp[maxn],het[maxn];int lg[maxn],St[maxn][20];int ans=0,L,n,m;int a[200005][2],b[200005][2];inline void qsort() { ???for(re int i=0;i<=m;i++) tax[i]=0; ???for(re int i=1;i<=L;i++) tax[rk[i]]++; ???for(re int i=1;i<=m;i++) tax[i]+=tax[i-1]; ???for(re int i=L;i;--i) sa[tax[rk[tp[i]]]--]=tp[i];}inline int ask(int l,int r) { ???int k=lg[r-l+1]; ???return min(St[l][k],St[r-(1<<k)+1][k]); }inline int LCP(int i,int j) { ???if(rk[i]>rk[j]) std::swap(i,j); ???return ask(rk[i]+1,rk[j]);}int main() { ???scanf("%d",&n); ???scanf("%s",A+1);scanf("%s",B+1); ???for(re int i=1;i<=n;i++) S[i]=A[i],a[i][0]=i; ???L=n+1;S[L]='$'; ???for(re int i=1;i<=n;i++)S[++L]=B[i],b[i][0]=L; ???S[++L]='#'; ???for(re int i=n;i;--i) S[++L]=A[i],a[i][1]=L; ???S[++L]='&'; ???for(re int i=n;i;--i) S[++L]=B[i],b[i][1]=L; ???for(re int i=1;i<=L;i++) rk[i]=S[i],tp[i]=i; ???m=255;qsort(); ???for(re int w=1,p=0;p<L;w<<=1,m=p) { ???????p=0; ???????for(re int i=1;i<=w;i++) tp[++p]=L-w+i; ???????for(re int i=1;i<=L;i++) if(sa[i]>w) tp[++p]=sa[i]-w; ???????qsort(); ???????for(re int i=1;i<=L;i++) std::swap(rk[i],tp[i]); ???????rk[sa[1]]=p=1; ???????for(re int i=2;i<=L;i++) ???????????rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p; ???} ???int k=0; ???for(re int i=1;i<=L;i++) { ???????if(k) --k; ???????int j=sa[rk[i]-1]; ???????while(S[i+k]==S[j+k]) ++k; ???????het[rk[i]]=k; ???} ???for(re int i=2;i<=L;i++) lg[i]=lg[i>>1]+1; ???for(re int i=1;i<=L;i++) St[i][0]=het[i]; ???for(re int j=1;j<=lg[L];j++) ????????for(re int i=1;i+(1<<j)-1<=L;i++) ????????????St[i][j]=min(St[i][j-1],St[i+(1<<(j-1))][j-1]); ???for(re int i=1;i<n;i++) { ???????int now=LCP(a[i+1][0],a[i][1]); ???????ans=max(2*now,ans); ???????if(i-now>=1) { ???????????int t=LCP(a[i-now][1],b[i+now][0]); ???????????ans=max(ans,2*(now+t)); ???????} ???} ???for(re int i=1;i<n;i++) { ???????int now=LCP(b[i+1][0],b[i][1]); ???????ans=max(2*now,ans); ???????if(i+now+1<=n) { ???????????int t=LCP(b[i+1+now][0],a[i-now+1][1]); ???????????ans=max(ans,2*(now+t)); ???????} ???} ???for(re int i=2;i<n;i++) { ???????int now=LCP(a[i+1][0],a[i-1][1]); ???????ans=max(2*now+1,ans); ???????if(i-now-1>=1) { ???????????int t=LCP(a[i-now-1][1],b[i+now][0]); ???????????ans=max(ans,2*(now+t)+1); ???????} ???} ???for(re int i=2;i<n;i++) { ???????int now=LCP(b[i+1][0],b[i-1][1]); ???????ans=max(2*now+1,ans); ???????if(i+now+1<=n) { ???????????int t=LCP(b[i+now+1][0],a[i-now][1]); ???????????ans=max(ans,2*(now+t)+1); ???????} ???} ???printf("%d\n",ans); ???return 0;}[JSOI2016]扭动的回文串
原文地址：https://www.cnblogs.com/asuldb/p/10628618.html