BZOJ4755 [Jsoi2016]扭动的回文串

Solution

考虑对于他给出的

A中的一个回文串；

B中的一个回文串；

或者某一个回文的扭动字符串S(i,j,k)

这样子几个限制,我们1,2就是很简单的manacher解决.

考虑第三个怎么做:

这一个扭动的回文串,一定是分成三个部分:A里面的,B里面的,A或B里的一个回文串.(串可以为空)

突然发现A或B里面的回文串可以选一个最大的,这样子对答案只会更优,不会变劣.

那么剩下的不难发现这是一个hash入门题(二分答案判断长度,终点已经确认(也就是长度和末端点在哪儿都确认了))

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=300010,base=19260817;int n;char a[N],b[N],c[N];typedef unsigned long long ull;ull pw[N],Hash[2][N];int f[2][N];void manacher(char *s,int *p){ int mx=0,id=0; s[0]='#'; for(int i=1;i<=n;i++){ p[i]=mx>i?min(p[2*id-i],mx-i):0; while(s[i-p[i]-1]==s[i+p[i]+1])p[i]++; if(i+p[i]>mx){ id=i;mx=i+p[i]; } }}ull calc(int w,int l,int r){ if(!w)return Hash[0][r]-Hash[0][l-1]*pw[r-l+1]; else return Hash[1][l]-Hash[1][r+1]*pw[r-l+1];}int ef(int L,int R){ int l=1,r=min(L,n-R+1),ans=0; while(l<=r){ int mid=(l+r)>>1; if(calc(0,L-mid+1,L)==calc(1,R,R+mid-1)){ans=mid;l=mid+1;} else r=mid-1; } return ans;}int main(){ n=gi(); scanf("%s",a+1);scanf("%s",b+1);pw[0]=1; for(int i=1;i<=n;i++)pw[i]=pw[i-1]*base; for(int i=1;i<=n;i++) Hash[0][i]=Hash[0][i-1]*base+a[i]; for(int i=n;i>=1;i--) Hash[1][i]=Hash[1][i+1]*base+b[i]; for(int i=1;i<=n;i++)c[i]=a[i]; for(int i=1,j=0;i<=n;i++)a[++j]='#',a[++j]=c[i];a[n+n+1]='#'; for(int i=1;i<=n;i++)c[i]=b[i]; for(int i=1,j=0;i<=n;i++)b[++j]='#',b[++j]=c[i];b[n+n+1]='#'; n=n*2+1; manacher(a,f[0]);manacher(b,f[1]);int ans=0; for(int i=1;i<=n;i++){ int l=(i-f[0][i]+1)/2,r=(i+f[0][i])/2; ans=max(ans,f[0][i]+ef(l-1,r)*2); } for(int i=1;i<=n;i++){ int l=(i-f[1][i]+1)/2,r=(i+f[1][i])/2; ans=max(ans,f[1][i]+ef(l,r+1)*2); } printf("%d\n",ans); return 0;}