SDOI2017 文本校正

传送门

分为6种情况。 $ABC:$哈希$O(1)$判断 $CAB:$枚举$C$的位置，哈希判断$AB$，$O(n)$ $BCA:$枚举$A$的位置，哈希判断$BC$，$O(n)$

$CBA:$金策字符串算法选讲 如果$s=ab$，$a,b$都是回文串，称$s$为一个双回文串。 引理：如果$s$是一个双回文串，则存在一种拆分方法$s=ab$，使得$a$是$s$的最长回文前缀或$b$是$s$的最长回文后缀。 具体证明见上面链接。 然后这题就有一个$trick$：把$T$串反过来插入$S$串，也就是：$S^{\prime }=s_1{t}_n{s}_2{t}_{n-1}...s_{n-1}{t}_2{s}_n{t}_1$ 那么如果$T$串满足$CBA$的形式，$S^{\prime }$就一定是三个连续回文串组成的，并且每个回文串长度为偶数。因为$T$倒过来就是$A^R{B}^R{C}^R$了。那么先用$manacher$处理一下，然后可以枚举第一个回文串的右端点位置，接下来判断后面的能否形成一个双回文串。 发现还要预处理出每个点向右最长的回文串的右端点，$dp$一下即可。（最长回文前缀） 然后还要判断每个点右边的最近的回文后缀（最长回文后缀）。这个先处理出所有回文后缀的左端点，然后用一个队列存起来，从左往右扫的时候把超过的位置弹掉就行了。

$BAC:$ 先枚举$C$的位置，然后判断$AB$和$BA$。 相当于给出$T_1,T_2$，要构造出$T_1=s_1{s}_2,T_2=s_2{s}_1$ 如果把$T_2$像上面那样倒过来插入$T_1$，相当于是判断一个双回文串。 于是可以像上面一样写。 然而发现把上面的结论转化一下就相当于是：$T_1$的前缀，和$T_2$的后缀做一个最大匹配，以及$T_1$的后缀，和$T_1$的前缀做一个最大匹配，分别判断两种情况是否可行。 最大匹配的话相当于是一个$kmp$，增量法处理。以$S$前缀匹配$T$后缀为例。 $pos\_s$表示$S[1$ ~ $pos\_s]$ = $T[i-pos\_s+1$ ~ $i]$，然后$i$往后挪一个，就在$S$里面往后匹配，不匹配就跳$fail$。注意到$fail$的性质前缀等于后缀。所以在跳$fail$过程中始终保持着前后缀相等。找到相同位置后哈希判一下剩下的部分相不相同。

$ACB:$把上面那个倒过来。

于是这题就愉快地写完了。注意匹配失败的时候返回$false$。。 以及$checkCBA$里的初始化。

#include<bits/stdc++.h> #define ull unsigned long long #define re register #define cs const cs int N=1e6+10,oo=1e9+7; cs ull base=131; struct node{ int l,r; node(int _l=0,int _r=0){l=_l,r=_r;} }ans[3]; int Case,n,m,s[N],t[N];bool ok[N]; int nxt_s[N],nxt_t[N]; ull hash_s[N],hash_t[N],Pow[N]; namespace IO{ cs int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline char gc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;} template<typename T> inline T get(){ char ch=gc();T x=0; while(!isdigit(ch)) ch=gc(); while(isdigit(ch)) x=((x+(x<<2))<<1)+(ch^48),ch=gc(); return x; } inline int gi(){return get<int>();} } using IO::gi; inline void Min(int &x,int y){if(x>y)x=y;} inline void Max(int &x,int y){if(x<y)x=y;} inline int min(int x,int y){return x<y?x:y;} inline int max(int x,int y){return x>y?x:y;} inline int collect(ull *a,int l,int r){return a[r]-a[l-1]*Pow[r-l+1];} inline int comp(ull *a,int l,ull *b,int x,int len){return collect(a,l,l+len-1)==collect(b,x,x+len-1);} inline void get_nxt(int *S,int *nxt){ int j=0;nxt[1]=0; for(int re i=2;i<=n;++i){ while(j&&S[i]!=S[j+1]) j=nxt[j]; nxt[i]=(j+=(S[i]==S[j+1])); } } inline bool checkABC(){ if(hash_s[n]==hash_t[n]){ ans[0]=node(1,1),ans[1]=node(2,2),ans[2]=node(3,n); return true; }return false; } inline bool checkACB(){ ok[0]=true; for(int re i=1;i<=n;++i) ok[i]=(s[i]==t[i])&&ok[i-1]; for(int re i=n,pos_s=n+1,pos_t=n+1;i>=1;--i){ while(pos_s!=n+1&&s[pos_s-1]!=t[i]) pos_s=n+1-nxt_s[n+1-pos_s]; pos_s-=(s[pos_s-1]==t[i]); while(pos_t!=n+1&&t[pos_t-1]!=s[i]) pos_t=n+1-nxt_t[n+1-pos_t]; pos_t-=(t[pos_t-1]==s[i]); if(!ok[i-1]) continue; int len_s=n-pos_s+1,len_t=n-pos_t+1; if(collect(hash_s,i,n-len_s)==collect(hash_t,i+len_s,n)){ ans[0]=node(1,i-1),ans[1]=node(i+len_s,n),ans[2]=node(i,i+len_s-1); return true; } if(collect(hash_t,i,n-len_t)==collect(hash_s,i+len_t,n)){ ans[0]=node(1,i-1),ans[1]=node(n-len_t+1,n),ans[2]=node(i,n-len_t); return true; } }return false; } inline bool checkBAC(){ ok[n+1]=true; for(int re i=n;i>=1;--i) ok[i]=(s[i]==t[i])&&ok[i+1]; for(int re i=1,pos_s=0,pos_t=0;i<=n;++i){ while(pos_s&&s[pos_s+1]!=t[i]) pos_s=nxt_s[pos_s]; pos_s+=(s[pos_s+1]==t[i]); while(pos_t&&t[pos_t+1]!=s[i]) pos_t=nxt_t[pos_t]; pos_t+=(t[pos_t+1]==s[i]); if(!ok[i+1]) continue; if(comp(hash_t,1,hash_s,pos_s+1,i-pos_s)){ ans[0]=node(i-pos_s+1,i),ans[1]=node(1,i-pos_s),ans[2]=node(i+1,n); return true; } if(comp(hash_s,1,hash_t,pos_t+1,i-pos_t)){ ans[0]=node(pos_t+1,i),ans[1]=node(1,pos_t),ans[2]=node(i+1,n); return true; } }return false; } inline bool checkBCA(){ for(int re len=1;len<=n-2;++len){ if( collect(hash_s,1,len)==collect(hash_t,n-len+1,n) and collect(hash_s,len+1,n)==collect(hash_t,1,n-len) ){ans[0]=node(n-len+1,n),ans[1]=node(1,1),ans[2]=node(2,n-len);return true;} }return false; } inline bool checkCAB(){ for(int re len=1;len<=n-2;++len){ if( collect(hash_s,n-len+1,n)==collect(hash_t,1,len) and collect(hash_s,1,n-len)==collect(hash_t,len+1,n) ){ans[0]=node(len+1,len+1),ans[1]=node(len+2,n),ans[2]=node(1,len);return true;} }return false; } int st[N<<2],top,S[N<<2],R[N<<2],rpos[N<<2];bool vis[N<<2]; int q[N<<2],qn; inline void manacher(int *S,int *R,int up){ int pos=0,mx=0; for(int re i=0;i<=up;++i){ R[i]=(mx>i)?(min(R[(pos<<1)-i],mx-i)):1; while(i-R[i]>=0&&(S[i-R[i]]==S[i+R[i]])) ++R[i]; if(mx<i+R[i]) mx=i+R[i],pos=i; Max(rpos[i-R[i]+1],i+R[i]-1); if(i+R[i]-1==top) vis[i-R[i]+1]=true; } } //双偶回文 inline bool check(int l,int r){return l<r&&((r-l)%4==0);} //端点为-1 inline bool is_p(int l,int r){ if(l>r) return false; int mid=(l+r)>>1; return (mid-R[mid]+1<=l); } inline bool checkCBA(){ top=0,qn=0; for(int re i=1;i<=n;++i) st[++top]=s[i],st[++top]=t[n+1-i]; for(int re i=1;i<=top;++i) S[(i-1)<<1]=-1,S[(i-1)<<1|1]=st[i]; S[top<<=1]=-1; for(int re i=0;i<=top;i+=2) rpos[i]=0,vis[i]=false; manacher(S,R,top); for(int re i=2;i<=top;i+=2){ Max(rpos[i],rpos[i-2]-2); if(vis[i]) q[++qn]=i; } // rpos[i]:i向右最长回文串的右端点 int head=1; for(int re i=4;i<=top;i+=4) if(is_p(0,i)){ while(q[head]<i) ++head; if(check(i,rpos[i])){ if(check(rpos[i],top)&&is_p(rpos[i],top)){ int lenA=i/4,lenC=(top-rpos[i])/4; ans[0]=node(n-lenA+1,n),ans[1]=node(lenC+1,n-lenA),ans[2]=node(1,lenC); return true; } } if(check(q[head],top)){ if(check(i,q[head])&&is_p(i,q[head])){ int lenA=i/4,lenC=(top-q[head])/4; ans[0]=node(n-lenA+1,n),ans[1]=node(lenC+1,n-lenA),ans[2]=node(1,lenC); return true; } } }return false; } inline void print(){ puts("YES"); printf("%d %d\n",ans[0].l,ans[0].r); printf("%d %d\n",ans[1].l,ans[1].r); printf("%d %d\n",ans[2].l,ans[2].r); } int main(){ // freopen("3154.in","r",stdin); // freopen("my.out","w",stdout); Case=gi(),Pow[0]=1; for(int re i=1;i<N;++i) Pow[i]=Pow[i-1]*base; while(Case--){ n=gi(),m=gi(); for(int re i=1;i<=n;++i) s[i]=gi(),hash_s[i]=hash_s[i-1]*base+s[i]; for(int re i=1;i<=n;++i) t[i]=gi(),hash_t[i]=hash_t[i-1]*base+t[i]; get_nxt(s,nxt_s),get_nxt(t,nxt_t); if(checkABC()) print(); else if(checkBCA()) print(); else if(checkCAB()) print(); else if(checkACB()) print(); else if(checkBAC()) print(); else if(checkCBA()) print(); else puts("NO"); } }