【BZOJ4556】[TJOI2016&HEOI2016] 字符串（后缀自动机+线段树合并+二分）

我会带着你远行 2021-10-15 03:59 233阅读 0赞

[点此看题面][Link 1]

**大致题意：** 给你一个字符串\\(s\\)，每次问你一个子串\\(s\[a..b\]\\)的所有子串和\\(s\[c..d\]\\)的最长公共前缀。

### 二分 ###

首先我们可以发现一个简单性质，即要求最长公共前缀，则我们必然取\\(s\[a..b\]\\)的一个子串\\(s\[x..b\]\\)，因为求最长公共前缀取长了不会影响答案。

那么如果我们二分答案\\(mid\\)，就变成了每次判断原串第\\(c\\)个后缀长度为\\(mid\\)的前缀是否是原串第\\(a\\sim b-mid+1\\)个后缀中某一后缀的前缀。

### 后缀自动机+线段树合并 ###

考虑我们先建一棵后缀树（就是对原串的倒串建一个[后缀自动机][Link 2]）。

然后，我们对于每一个节点，开一棵线段树维护其子树内有哪些后缀。

这可以通过线段树合并轻松预处理。

接下来，对于每次判断，我们找到第\\(c\\)个后缀所对应的节点，树上倍增找到其祖先中长度大于等于\\(mid\\)且长度最小的祖先，然后判断其子树内是否存在第\\(a\\sim b-mid+1\\)个后缀中的某一后缀即可。

### 代码 ###

#include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI int #define Con const #define CI Con int& #define I inline #define W while #define N 100000 #define LN 20 #define min(x,y) ((x)<(y)?(x):(y)) using namespace std; int n;string s; class FastIO { private: #define FS 100000 #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++) #define pc(c) (C==E&&(clear(),0),*C++=c) #define tn (x<<3)+(x<<1) #define D isdigit(c=tc()) int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS]; public: I FastIO() {A=B=FI,C=FO,E=FO+FS;} Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);} Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);} I void reads(string& x) {x="";W(isspace(c=tc()));W(x+=c,!isspace(c=tc())&&~c);} Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);} Tp I void writeln(Con Ty& x) {write(x),pc('\n');} I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;} }F; template<int SZ> class SuffixAutomation//后缀自动机 { private: template<int PS> class SegmentTree//线段树 { private: #define L l,mid,S[rt][0] #define R mid+1,r,S[rt][1] #define PU(x) (V[x]=V[S[x][0]]|V[S[x][1]]) int n,tot,S[PS+5][2],V[PS+5]; I void Ins(CI p,CI l,CI r,int& rt)//插入元素 { if(!rt&&(rt=++tot),l==r) return (void)(V[rt]=1);RI mid=l+r>>1; p<=mid?Ins(p,L):Ins(p,R),PU(rt); } I bool Check(CI tl,CI tr,CI l,CI r,CI rt)//检验tl~tr之间是否有1 { if(!rt) return 0;if(tl<=l&&r<=tr) return V[rt];RI mid=l+r>>1; return (tl<=mid&&Check(tl,tr,L))||(tr>mid&&Check(tl,tr,R)); } I int Merge(CI x,CI y,CI l,CI r)//线段树合并 { if(!x||!y) return x+y;RI rt=++tot,mid=l+r>>1;V[rt]=V[x]|V[y];if(l==r) return rt; S[rt][0]=Merge(S[x][0],S[y][0],l,mid),S[rt][1]=Merge(S[x][1],S[y][1],mid+1,r);return rt; } public: I void Init(CI _n) {n=_n;}I void Ins(int& rt,CI p) {Ins(p,1,n,rt);} I int Merge(CI x,CI y) {return Merge(x,y,1,n);} I int Check(CI rt,CI l,CI r) {return Check(l,r,1,n,rt);} #undef L }; int n,lst,tot,pos[SZ+5],s[SZ<<1],t[SZ<<1];struct node {int Rt,L,F[LN],S[30];}O[SZ<<1]; SegmentTree<SZ*LN<<1> S; public: I SuffixAutomation() {lst=tot=1;}I void Init(CI _n) {S.Init(n=_n);} I void Insert(CI id,CI x)//插入元素 { RI now=++tot,p=lst,q;O[pos[id]=now=lst=tot].L=O[p].L+1,S.Ins(O[now].Rt,id); W(p&&!O[p].S[x]) O[p].S[x]=now,p=O[p].F[0];if(!p) return (void)(O[now].F[0]=1); if(O[p].L+1==O[q=O[p].S[x]].L) return (void)(O[now].F[0]=q); RI k=++tot;O[k].L=O[p].L+1,O[k].F[0]=O[q].F[0],O[now].F[0]=O[q].F[0]=k, memcpy(O[k].S,O[q].S,sizeof(O[q].S));W(p&&O[p].S[x]==q) O[p].S[x]=k,p=O[p].F[0]; } I void Work()//预处理 { #define Rsort() for(i=1;i<=tot;++i) ++t[O[i].L];\ for(i=1;i<=n;++i) t[i]+=t[i-1];for(i=tot;i;--i) s[t[O[i].L]--]=i;//基数排序 RI i,j;Rsort();for(i=1;i<=tot;++i) for(j=1;j<=LN;++j) O[s[i]].F[j]=O[O[s[i]].F[j-1]].F[j-1];//预处理倍增祖先 for(i=tot;i;--i) O[s[i]].F[0]&&(O[O[s[i]].F[0]].Rt=S.Merge(O[O[s[i]].F[0]].Rt,O[s[i]].Rt));//线段树合并，处理子树内有哪些后缀 } I bool Check(CI k,CI l,CI r,CI id)//检验 { RI i,x=pos[id];for(i=LN;~i;--i) O[O[x].F[i]].L>=k&&(x=O[x].F[i]);//倍增找到合法祖先 return S.Check(O[x].Rt,l,r);//线段树上查询 } }; SuffixAutomation<N> S; int main() { RI Qt,i,x1,y1,x2,y2,l,r,mid;F.read(n,Qt),F.reads(s); for(S.Init(n),i=n;i;--i) S.Insert(i,s[i-1]&31);S.Work();W(Qt--)//建后缀自动机，注意用倒串 { F.read(x1,y1,x2,y2),l=0,r=min(y1-x1+1,y2-x2+1);//读入 W(l<r) mid=l+r+1>>1,S.Check(mid,x1,y1-mid+1,x2)?l=mid:r=mid-1;//二分 F.writeln(l);//输出 }return F.clear(),0; }

转载于:https://www.cnblogs.com/chenxiaoran666/p/BZOJ4556.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=4556
[Link 2]: https://www.cnblogs.com/chenxiaoran666/p/SuffixAutomation.html