作为一道码农题……

(SA+二分套(主席树+二分))怕不是真·理论复杂度O(Nlog^2N)

如果熟练的压行的话应该可以做到百行以内吧

那么我们来讲解一下这道题：设我们的答案为mid(注意这里有坑是[a,b]的所有子串和[c,d]这个子串的最长lcp),那么我们会发现一个很有趣的事实: 如果mid可行的话，那么任意一个比mid小的数也可行

也就是说，问题满足可二分性，那么我们可以二分答案，将原问题转化为一个判定性问题:mid这个答案行不行？

那么我们发现，如果mid这个答案可以的话，就会存在一个后缀S，

1.它的开头在[a,b-mid+1]当中。

2.lcp(S,c)>=mid。

再次转化一步，就是询问满足以上两个条件的后缀S的个数，经典的二元限制统计问题，我们的思路很简单，摁死一个再去管下一个，发现一件有趣的事实：如果把这些后缀排好序，那么lcp符合要求的一定是一段连续的区间，(为什么？，因为我们发现排好序以后，lcp这个函数是单峰的，并且峰值在自己这里)

那么我们似乎可以二分左端点和右端点，为此我们需要O(1)求出区间最小值，为此我们还得写一个St表QAQ

那么最后我们发现现在两个限制都是区间型的了，而且是静态区间，没有修改，所以可以用主席树查询一发……

下面是科普

只是介绍一些关于数据结构/算法的引申，并不会详细介绍原理，如果不会的话看对应的膜板吧，解释的都很详细

关于后缀数组

ht数组的意义是，lcp(rk[i-1],rk[i])，所以ht数组是在按sa序排出来之后才有意义的，另外我们会发现ht数组是“向上”匹配的，所以我们使用区间min来查询任意两个串的lcp时查询的是(rk[a],rk[b]]即左开右闭区间。

关于st表

考虑到ht数组向上匹配的特性，我们的区间min也写成左开右闭就好了

关于主席树

主席树其实是线段树的前缀和，我们的线段树通常是一个权值线段树以满足我们对权值的区间限制要求，那么我们建主席树的时候通常是一个点一个点插入，以满足每一个实际区间的要求，对于这道题来讲，我们对sa建主席树，因为最后实际上第二次二分的区间是一个在sa序上连续的区间，查询限制的则是这个后缀的实际编号，所以我们的权值线段树的权值是后缀的编号。

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;int n;int m;
char mde[N];int sa[N];int rk[2*N];int ht[N];
int x[N];int y[N];queue <int> q[N];
inline bool cmp(int i,int j){return (x[i]==x[j])&&(y[i]==y[j]);}
inline void rixs()//这里的后缀数组用的是队列实现，常数较大
{
    for(int i=1;i<=n;i++){q[y[i]].push(i);}
    int cnt=0;for(int i=0;i<=n;i++)
    {for(;!q[i].empty();q[i].pop()){sa[++cnt]=q[i].front();}}
    for(int i=1;i<=n;i++){q[x[sa[i]]].push(sa[i]);}
    cnt=0;for(int i=0;i<=n;i++)
    {for(;!q[i].empty();q[i].pop()){sa[++cnt]=q[i].front();}}
    rk[sa[1]]=1;for(int i=2;i<=n;i++)
    {rk[sa[i]]=(cmp(sa[i-1],sa[i]))?rk[sa[i-1]]:i;}
}
inline void create_sa()//板子啥的问度娘吧
{
    for(int i=1;i<=n;i++){q[mde[i]-'a'+1].push(i);}
    int cnt=0;for(int i=1;i<=26;i++)
    {for(;!q[i].empty();q[i].pop()){sa[++cnt]=q[i].front();}}
    rk[sa[1]]=1;for(int i=2;i<=n;i++)
    {rk[sa[i]]=(mde[sa[i-1]]==mde[sa[i]])?rk[sa[i-1]]:i;}
    for(int k=1;k<=n;k*=2)
    {for(int i=1;i<=n;i++){x[i]=rk[i];y[i]=rk[i+k];}rixs();}
}
inline void calch()
{
    int j=0;int k=0;for(int i=1;i<=n;ht[rk[i++]]=k)
    {for(k=k?k-1:k,j=sa[rk[i]-1];mde[i+k]==mde[j+k];k++);}
}
int st[22][N];int log[N];
inline void calclog()//打表log，方便使用
{int i=0;for(int j=1;j<=n;j++){if((1<<(i+1))<=j)i++;log[j]=i;}}
inline void create_st()//对ht建st表
{
    for(int i=0;i<=n-1;i++){st[0][i]=ht[i+1];}
    for(int i=1;i<=log[n];i++)
    {for(int j=0;j<n-(1<<(i-1));j++){st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);}}
}
inline int rmq(int l,int r)//左开右闭的rmq
{int len=r-l;int res=min(st[log[len]][l],st[log[len]][r-(1<<log[len])]);return res;}
struct per_linetree//主席树的板子，这个真的是纯板子了
{
    int s[2][44*N];int fa[44*N];int root[N];int cnt;int val[44*N];
    per_linetree(){root[0]=1;cnt=1;}
    inline void insert(int p1,int p2,int l,int r,int pos)
    {
        val[p2]=val[p1]+1;if(r-l==1)return;int mid=(l+r)/2;
        if(pos<=mid){s[0][p2]=++cnt;s[1][p2]=s[1][p1];insert(s[0][p1],cnt,l,mid,pos);}
        else {s[1][p2]=++cnt;s[0][p2]=s[0][p1];insert(s[1][p1],cnt,mid,r,pos);}
    }
    inline void add(int t1,int t2,int pos)
    {root[t2]=++cnt;insert(root[t1],root[t2],0,n,pos);}
    inline int sum(int p1,int p2,int l,int r,int dl,int dr)
    {
        if(dl==l&&dr==r){return val[p2]-val[p1];}int mid=(l+r)/2;int res=0;
        if(dl<mid)res+=sum(s[0][p1],s[0][p2],l,mid,dl,min(dr,mid));
        if(mid<dr)res+=sum(s[1][p1],s[1][p2],mid,r,max(dl,mid),dr);
        return res;
    }
    inline int query(int t1,int t2,int l,int r)
    {return sum(root[t1-1],root[t2],0,n,l-1,r);}
}plt;
inline bool jud(int x,int a,int b,int c)//检测mid是否可行
{
    int l=1;int r=rk[c];int up;int down;//二分上边界，注意是左开右闭
    while(l<r){int mid=(l+r)/2;if(rmq(mid,rk[c])<x){l=mid+1;}else {r=mid;}}
    up=r;
    l=rk[c];r=n;//二分下边界
    while(l<r){int mid=(l+r+1)/2;if(rmq(rk[c],mid)<x){r=mid-1;} else{l=mid;}}
    down=r;
    return plt.query(up,down,a,b-x+1)!=0;//主席树查一发是否存在符合要求的后缀
}
inline int solve(int a,int b,int c,int d)//主二分过程
{
    int l=0;int r=min(b-a+1,d-c+1);//这个就是裸的二分答案了
    while(l<r){int mid=(l+r+1)/2;if(jud(mid,a,b,c)){l=mid;}else {r=mid-1;}}
    return r;
}
int main()
{
    scanf("%d%d",&n,&m);scanf("%s",mde+1);
    create_sa();calch();calclog();create_st();//上来先预处理
    for(int i=1;i<=n;i++){plt.add(i-1,i,sa[i]);}//对sa建主席树
    for(int i=1;i<=m;i++)
    {
        int a;int b;int c;int d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        printf("%d\n",solve(a,b,c,d));
    }return 0;//拜拜程序~
}

P4094 [HEOI2016/TJOI2016]字符串 题面传送门

题意简述：给出字符串 $s$，多次询问 $a,b,c,d$ 求 $s[a:b]$ 的所有子串与 $s[c:d]$ 的最长公共前缀的最大值。

我的 SAM 学习笔记 例题 X.

首先，SAM 不太方便处理前缀，所以将整个串翻转（询问不要忘记翻转），这样就转化为了最长公共后缀。接下来求 $s[1:d]$ 所代表的状态，设为 $p$，直接在建 SAM 时预处理即可。

直接不管 $c$ 的限制，问题转化为求出 $s[a:b]$ 所有子串与 $s[1:d]$ 的最长公共后缀长度，并与 $d-c+1$ 取 $\min$。

根据 SAM 的性质，$link$ 树上所有 $p$ 的祖先都表示 $s[1:d]$ 的一个或多个后缀。我们可以找到一个状态 $q$ 满足 $q$ 是 $p$ 的祖先且 $\left(\max_{x\in endpos(q),x\leq b}x\right)-a+1\leq len(q)$（也就是该状态所表示的字符串在 $b$ 或 $b$ 之前出现的最靠右的结束位置，至于为什么要最靠右显而易见（右边的出现位置肯定优于左边的出现位置，因为有左端点 $a$ 的限制），读者可自行理解），且 $len(q)$ 的值最小，那么最长公共后缀肯定在 $q$ 或 $link(q)$ 所表示的子串中。

• 先说说为什么要 $len(q)$ 最小：假设存在 $q'$ 满足上述条件，但 $len(q')>len(q)$，即 $q$ 是 $q'$ 的祖先（同时 $q'$ 是 $p$ 的祖先）。记 $\max_{x\in endpos(q),x\leq b}x$ 为 $maxp(q,b)$，那么根据 $endpos$ 和 $link$ 的性质，即 $endpos(q')\subsetneq endpos(q)$，因此，$maxp(q',b)\leq maxp(q,b)$，即 $q'$ 点所表示字符串在 $b$ 或 $b$ 之前出现的最大结束位置，一定不大于 $q$ 点所表示的字符串在 $b$ 或 $b$ 之前出现的最大结束位置。因此 $maxp(q',b)-a+1\leq maxp(q,b)-a+1$。又因为 $len(q)\ (len(q'))\geq maxp(q,b)\ (maxp(q',b)) -a+1$，即 $q$ 和 $q'$ 所表示的的最长字符串超出了 $a$ 的限制，所以我们是用 $maxp$ 值 $-a+1$ 求出在 $a$ 的限制下该状态对答案的贡献。故 $q$ 一定比 $q'$ 更优。

• 再说说为什么要算上 $link(q)$： 一 目 了 然，不 言 而 喻。

• 同时，因为 $link(q)$ 的贡献已经是 $len(q)$ 了，如果再往上跳 $maxp$ 递增，贡献也一定是该点的 $len$ 值，这是递减的，所以不需要再往上考虑。

说完了思路，接下来讲讲怎么实现：用线段树合并维护 $endpos$ 集合可以轻松在 $\log$ 时间内求出 $maxp$。同时，因为满足条件的 $q$ 满足二分条件，所以求 $q$ 直接用 $p$ 在 $link$ 树上倍增即可。那么最后答案即为 $\min(\max(maxp(q,b)-a+1,len(link(q))),d-c+1)$。（不需要特判答案为 $0$ 的情况，因为此时 $maxp(q,b)-a+1$ 不小于 $0$，而 $len(link(q))$ 显然为 $0$）

时间复杂度 $\mathcal{O}(q\log^2 n)$。

/*
	Powered by C++11.
	Author : Alex_Wei.
*/

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize(3)

//using int = long long
//using i128 = __int128;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using pii = pair <int,int>;
using pll = pair <ll,ll>;
using pdd = pair <double,double>;
using vint = vector <int>;
using vpii = vector <pii>;

#define fi first
#define se second
#define pb emplace_back
#define mpi make_pair
#define all(x) x.begin(),x.end()
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define mem(x,v) memset(x,v,sizeof(x))
#define mcpy(x,y) memcpy(x,y,sizeof(y))
#define Time 1.0*clock()/CLOCKS_PER_SEC

pii operator + (pii a,pii b){return {a.fi+b.fi,a.se+b.se};}
pll operator + (pll a,pll b){return {a.fi+b.fi,a.se+b.se};}

namespace IO{
	char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<24],*O=obuf;
	#ifdef __WIN32
		#define gc getchar()
	#else
		#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
	#endif
	#define pc(x) (*O++=x)
	#define flush() fwrite(obuf,O-obuf,1,stdout)
	inline ll read(){
		ll x=0; bool sign=0; char s=gc;
		while(!isdigit(s))sign|=s=='-',s=gc;
		while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
		return sign?-x:x;
	}
	inline void print(ll x){
		if(x<0)pc('-'),print(-x);
		else{
			if(x>9)print(x/10);
			pc(x%10+'0');
		}
	}
} using namespace IO;

const int N=2e5+5;
const int S=26;

int node,rt[N],ls[N<<5],rs[N<<5],val[N<<5];
void push(int x){
	val[x]=max(val[ls[x]],val[rs[x]]);
} void ins(int l,int r,int p,int &x){
	x=++node;
	if(l==r)return val[x]=p,void();
	int m=l+r>>1;
	if(p<=m)ins(l,m,p,ls[x]);
	else ins(m+1,r,p,rs[x]);
	push(x);
} int merge(int l,int r,int x,int y){
	if(!x||!y)return x|y;
	int z=++node,m=l+r>>1;
	if(l==r)return val[z]=max(val[x],val[y]),z;
	ls[z]=merge(l,m,ls[x],ls[y]),rs[z]=merge(m+1,r,rs[x],rs[y]);
	return push(z),z;
} int query(int l,int r,int ql,int qr,int x){
	if(!x)return 0;
	if(ql<=l&&r<=qr)return val[x];
	int m=l+r>>1,ans=0;
	if(ql<=m)ans=query(l,m,ql,qr,ls[x]);
	if(m<qr)ans=max(ans,query(m+1,r,ql,qr,rs[x]));
	return ans;
}

// Suffix_Automaton
int a,b,c,d;
int n,m,K,cnt,las;
int fa[N],len[N],son[N][S];
int buc[N],id[N],f[N][S],ed[N];
vector <int> e[N];
void ins(int it){
	int p=las,cur=++cnt;
	len[cur]=len[las]+1,las=cur;
	ins(1,n,len[cur],rt[cur]),ed[len[cur]]=cur;
	while(p&&!son[p][it])son[p][it]=cur,p=fa[p];
	if(!p)return fa[cur]=1,void();
	int q=son[p][it];
	if(len[p]+1==len[q])return fa[cur]=q,void();
	int cl=++cnt;
	fa[cl]=fa[q],fa[q]=fa[cur]=cl,len[cl]=len[p]+1;
	mcpy(son[cl],son[q]);
	while(p&&son[p][it]==q)son[p][it]=cl,p=fa[p];
} void build(char *s){
	las=cnt=1,K=log2(n);
	for(int i=1;i<=n;i++)ins(s[i]-'a');
	for(int i=1;i<=cnt;i++)buc[len[i]]++;
	for(int i=1;i<=n;i++)buc[i]+=buc[i-1];
	for(int i=cnt;i;i--)id[buc[len[i]]--]=i;
	for(int i=cnt;i>1;i--)rt[fa[id[i]]]=merge(1,n,rt[fa[id[i]]],rt[id[i]]);
	for(int j=0;j<=K;j++)for(int i=1;i<=cnt;i++)f[i][j]=j?f[f[i][j-1]][j-1]:fa[i];
} int qpos(int pos){
	return query(1,n,1,b,rt[pos]);
}

char s[N];
int main(){
	cin>>n>>m,scanf("%s",s+1);
	reverse(s+1,s+n+1),build(s);
	while(m--){
		cin>>a>>b>>c>>d;
		a=n-a+1,b=n-b+1,c=n-c+1,d=n-d+1,swap(a,b),swap(c,d);
		int p=ed[d];
		for(int i=K;~i;i--)if(f[p][i]){
			int pp=f[p][i],pos=qpos(pp);
			if(len[pp]>=pos-a+1)p=pp;
		} int pos=qpos(p);
		cout<<min(d-c+1,max(pos-a+1,len[f[p][0]]))<<endl;
	}
	return 0;
}