\(\text{Solution:}\)
求一个字符串一段区间与 \(t\) 的最长公共子串。
考虑 SAM 与 AC 自动机相似的性质，按照惯例 ，我们先对 \(t\) 建立 SAM ，在上面跑出对 \(s\) 的每个前缀，其能与 \(t\) 匹配的，以 \(s_i\) 结尾的最长公共子串长度 \(mt_i\) 。
关于匹配的过程就直接在 SAM 上面跳就好了。注意如果跳到根还没有对应出边的话匹配长度就是 \(0.\)
那么知道了 \(mt_i,\) 答案就被转化为：
\[\max_{i=l}^r \min\{i-l+1,mt_i\} \]最小值最大……二分。
观察，如果满足 \(\min\) 取 \(mt_i,\) 那么必然有：
\[i-l+1\ge mt_i \\ i-mt_i+1\ge l \]那么，不等式的右侧是一个定值，观察左侧：\(i\) 每次会单增 \(1,\) 但是注意，\(mt_i\) 的最大增长就是 \(+1,\) 其余要么不变要么变小。
所以， \(i-mt_i+1\) 是一个不降的序列！
那么必然存在一个位置 \(pos\) 满足 \(\forall i\ge pos,\min\{i-l+1,mt_i\}=mt_i,\forall i<pos,\min\{i-l+1,mt_i\}=i-l+1\)
那 \(pos\) 显然是满足 \(i-mt_i+1\ge l\) 的最小的 \(pos.\) 又因为那东西不降，直接二分即可。
最后的答案就是 \(\max\{pos-l,\max_{i=pos}^r mt_i\},\) 后面的 \(\max\) 可以用 st表 做到 \(O(1).\)
总时间复杂度就是 \(O(n\log n).\)
一个细节：之前看某篇博客上面讲的是对 \(S\) 建立 SAM 求出 \(T\) 在上面每个前缀匹配到的后缀长度。由于笔者脑子不好使 一时间没有发觉这是错的，实际上这样匹配出来的没有对应询问的区间限制，显然是错误的。
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
char s[N],t[N],q;
int slen,tlen,mt[N],f[N][20];
inline int Min(int x,int y){return x<y?x:y;}
inline int Max(int x,int y){return x>y?x:y;}
namespace SAM{
int len[N],pa[N],ch[N][26],last=1,tot=1;
void insert(const int &c){
int p=last;
int np=++tot;
last=tot;
len[np]=len[p]+1;
for(;p&&!ch[p][c];p=pa[p])ch[p][c]=np;
if(!p)pa[np]=1;
else{
int q=ch[p][c];
if(len[q]==len[p]+1)pa[np]=q;
else{
int nq=++tot;
len[nq]=len[p]+1;
pa[nq]=pa[q];pa[q]=pa[np]=nq;
memcpy(ch[nq],ch[q],sizeof ch[q]);
for(;p&&ch[p][c]==q;p=pa[p])ch[p][c]=nq;
}
}
}
void Do(){
int now=1;
for(int i=1;i<=tlen;++i){
int v=t[i]-'a';
if(ch[now][v])mt[i]=mt[i-1]+1,now=ch[now][v];
else{
while(now&&!ch[now][v])now=pa[now];
if(!now)now=1;
else mt[i]=len[now]+1,now=ch[now][v];
}
}
}
}
int lg[N],qq;
int query(int l,int r){
if(l>r)return 0;
int k=lg[r-l+1];
return Max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
scanf("%s",s+1);
scanf("%s",t+1);
swap(s,t);
slen=strlen(s+1);
tlen=strlen(t+1);
for(int i=1;i<=slen;++i)SAM::insert(s[i]-'a');
// puts("SAM?");
SAM::Do();
// puts("mate len:");
// for(int i=1;i<=tlen;++i)printf("%d ",mt[i]);
// puts("");
// puts("MATE?");
lg[0]=-1;
for(int i=1;i<=tlen;++i)lg[i]=lg[i>>1]+1,f[i][0]=mt[i];
for(int i=1;(1<<i)<=tlen;++i){
for(int j=1;j+(1<<i)-1<=tlen;++j){
f[j][i]=Max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
}
// puts("ST?");
scanf("%d",&qq);
while(qq--){
int ql,qr;
scanf("%d%d",&ql,&qr);
int pos=qr+1;
int R=qr,L=ql;
while(ql<=qr){
int mid=(ql+qr)>>1;
if(mid-mt[mid]+1>=L)qr=mid-1,pos=mid;
else ql=mid+1;
}
printf("%d\n",Max(query(pos,R),pos-L));
}
return 0;
}