bzoj4556: [Tjoi2016&Heoi2016]字元串（二分答案+sam+線段樹合并）

傳送門

題意：給一個字元串 S S S。

有 m m m次詢問，每次給四個參數 a , b , c , d a,b,c,d a,b,c,d，問 s [ a . . . b ] s[a...b] s[a...b]的所有子串和 s [ x . . . y ] s[x...y] s[x...y]的最長公共字首是多少。

思路：先翻轉字元串轉化為求最長公共字尾。

設現在求 s [ a . . . b ] s[a...b] s[a...b]的所有子串和 s [ x . . . y ] s[x...y] s[x...y]的最長公共字尾是多少。

然後二分答案，設最長公共字尾為 s [ y − m i d + 1... y ] s[y-mid+1...y] s[y−mid+1...y]，我們在反串的 s a m sam sam倍增找到這個串對應的節點，然後如果存在 s [ a . . b ] s[a..b] s[a..b]的子串那麼這個子串的右端點一定在這個倍增出的節點的 r i g h t right right集合中，于是對于每個節點用線段樹合并處理出它對應的 r i g h t right right集合最後查詢即可。

代碼：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=3e5+5,M=5e6+5;
int rt[N],pos[N],st[N][20],n,m;
namespace SGT{
	#define lc (son[p][0])
	#define rc (son[p][1])
	#define mid (l+r>>1)
	int son[M][2],tot=0;
	bool exi[M];
	inline void build(int&p,int l,int r,int k){
		if(!p)p=++tot;
		exi[p]=1;
		if(l==r)return;
		k<=mid?build(lc,l,mid,k):build(rc,mid+1,r,k);
	}
	inline int merge(int x,int y,int l,int r){
		if(!x||!y)return x+y;
		int p=++tot;
		exi[p]=exi[x]|exi[y];
		if(l==r)return p;
		lc=merge(son[x][0],son[y][0],l,mid);
		rc=merge(son[x][1],son[y][1],mid+1,r);
		return p;
	}
	inline bool query(int p,int l,int r,int ql,int qr){
		if(!exi[p])return 0;
		if(ql<=l&&r<=qr)return exi[p];
		if(qr<=mid)return query(lc,l,mid,ql,qr);
		if(ql>mid)return query(rc,mid+1,r,ql,qr);
		return query(lc,l,mid,ql,qr)|query(rc,mid+1,r,ql,qr);
	}
	#undef lc
	#undef rc
	#undef mid
}
namespace sam{
	int link[N],len[N],son[N][26],tot=1,last=1;
	inline void expand(int x,int id){
		int p=last,np=++tot;
		pos[id]=last=np,len[np]=len[p]+1,SGT::build(rt[np],1,n,id);
		while(p&&!son[p][x])son[p][x]=np,p=link[p];
		if(!p){link[np]=1;return;}
		int q=son[p][x],nq;
		if(len[q]==len[p]+1){link[np]=q;return;}
		len[nq=++tot]=len[p]+1,link[nq]=link[q],memcpy(son[nq],son[q],sizeof(son[q]));
		link[q]=link[np]=nq;
		while(p&&son[p][x]==q)son[p][x]=nq,p=link[p];
	}
	inline void init(){
		static int cnt[N],rk[N];
		for(ri i=1;i<=tot;++i)st[i][0]=link[i];
		for(ri j=1;j<20;++j)for(ri i=1;i<=tot;++i)st[i][j]=st[st[i][j-1]][j-1];
		for(ri i=1;i<=tot;++i)++cnt[len[i]];
		for(ri i=1;i<=tot;++i)cnt[i]+=cnt[i-1];
		for(ri i=tot;i;--i)rk[cnt[len[i]]--]=i;
		for(ri i=tot;i^1;--i)rt[link[rk[i]]]=SGT::merge(rt[link[rk[i]]],rt[rk[i]],1,n);
	}
}
inline bool check(int a,int b,int lim,int r){
	int p=pos[r];
	for(ri i=19;~i;--i)if(sam::len[st[p][i]]>=lim)p=st[p][i];
	return SGT::query(rt[p],1,n,a,b);
}
char s[N];
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int main(){
	n=read(),m=read();
	scanf("%s",s+1),reverse(s+1,s+n+1);
	for(ri i=1;i<=n;++i)sam::expand(s[i]-'a',i);
	sam::init();
	for(ri i=1,a,b,x,y,l,r,mid,ans;i<=m;++i){
		b=n-read()+1,a=n-read()+1,y=n-read()+1,x=n-read()+1;
		l=1,r=min(b-a+1,y-x+1),ans=0;
		while(l<=r)if(mid=l+r>>1,check(a+mid-1,b,mid,y))l=mid+1,ans=mid;else r=mid-1;
		cout<<ans<<'\n';
	}
	return 0;
}