【HEOI2016】【TJOI2016】字符串（SAM）（线段树合并）（树上倍增）

传送门

题解：

询问的是 [ a , b ] [a,b] [a,b]的所有子串和 [ c , d ] [c,d] [c,d]整个串的LCP。

翻转一下变成LCS。由于是对于[c,d]整个串，我们二分答案之后树上倍增找到对应节点，看一下SAM这个点上right集合里面有没有我们要的[a,b-len+1]的串就行了。

求right集合需要线段树合并。

代码：

#include<bits/stdc++.h>
#define re register
#define cs const

using std::cerr;
using std::cout;

cs int N=1e5+7;

int n,m;char s[N];

namespace SGT{
	cs int N=::N*40;
	int lc[N],rc[N],tot;
	inline void ins(int &u,int l,int r,int p){
		u=++tot;if(l==r)return ;int mid=l+r>>1;
		(p<=mid)?ins(lc[u],l,mid,p):ins(rc[u],mid+1,r,p);
	}
	inline void merge(int &u,int v,int l=1,int r=n){
		if(!u||!v){u|=v;return ;}if(l==r)return ;
		int mid=l+r>>1,t=++tot;
		merge(lc[t]=lc[u],lc[v],l,mid);
		merge(rc[t]=rc[u],rc[v],mid+1,r);
		u=t;
	}
	inline int query(int u,int l,int r,int ql,int qr){
		if(!u)return false;
		if(ql<=l&&r<=qr)return true;
		int mid=l+r>>1;
		if(qr<=mid)return query(lc[u],l,mid,ql,qr);
		if(mid<ql)return query(rc[u],mid+1,r,ql,qr);
		return query(lc[u],l,mid,ql,qr)||query(rc[u],mid+1,r,ql,qr);
	}
}

namespace SAM{
	cs int N=::N<<1;
	int son[N][26],fa[N],len[N],last=1,now=1;
	int rt[N],bin[N],nd[N],f[21][N],ps[N];
	inline void push_back(int id,int c){
		int cur=++now,p=last;len[cur]=len[p]+1;
		for(;p&&!son[p][c];p=fa[p])son[p][c]=cur;
		if(!p)fa[cur]=1;
		else if(len[son[p][c]]==len[p]+1)fa[cur]=son[p][c];
		else {
			int nq=++now,q=son[p][c];
			memcpy(son[nq],son[q],sizeof son[q]);
			len[nq]=len[p]+1;
			fa[nq]=fa[q];fa[q]=fa[cur]=nq;
			for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
		}
		ps[id]=last=cur;SGT::ins(rt[cur],1,n,id);
	}
	inline void build(){
		for(int re i=1;i<=now;++i)f[0][i]=fa[i];
		for(int re i=1;i<=20;++i)
		for(int re u=1;u<=now;++u)f[i][u]=f[i-1][f[i-1][u]];
		
		for(int re i=1;i<=now;++i)++bin[len[i]];
		for(int re i=1;i<=now;++i)bin[i]+=bin[i-1];
		for(int re i=now;i;--i)nd[bin[len[i]]--]=i;
		for(int re i=now;i;--i)if(fa[nd[i]])SGT::merge(rt[fa[nd[i]]],rt[nd[i]]);
	}
	inline bool check(int u,int Len,int L,int R){u=ps[u];
		for(int re i=20;~i;--i)if(f[i][u]&&len[f[i][u]]>=Len)u=f[i][u];
		return SGT::query(rt[u],1,n,L+Len-1,R);
	}
}

signed main(){
#ifdef zxyoi
	freopen("string.in","r",stdin);
#endif
	scanf("%d%d%s",&n,&m,s+1);std::reverse(s+1,s+n+1);
	for(int re i=1;i<=n;++i)SAM::push_back(i,s[i]-'a');
	SAM::build();while(m--){
		int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
		a=n-a+1,b=n-b+1,c=n-c+1,d=n-d+1;
		int l=0,r=std::min(a-b+1,c-d+1),ans=0,mid;
		while(l<=r)SAM::check(c,mid=l+r>>1,b,a)?(l=mid+1,ans=mid):(r=mid-1);
		cout<<ans<<"\n";
	}
	return 0;
}