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

点此看题面

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

二分

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

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

后缀自动机+线段树合并

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

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

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

接下来，对于每次判断，我们找到第\(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;

}

巴特西

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

二分

后缀自动机+线段树合并

代码

最新文章

热门文章