题意：
给出两个只包含小写字母的字符串S,T，有q次询问，每次求$S_{lcdots r}$和$T$的最长公共子串长度。
$|S|,|T|,qleq 2 imes 10^5$。
题解：
挺水的一道题，给两位Au水平的选手出这个是认真的么……
首先考虑怎么求两个串a,b的最长公共子串：直接建出b的SAM，把a的每个后缀放上去跑。
直接跑是$O(n^{2})$的，考虑换个方式，对每个前缀i求出极大的$f_i$满足$S_{f_i cdots i}$是$T$的子串。
那么如果知道了$f_{i-1}$和$S_{f_{i-1} cdots i-1}$在SAM上所属的节点u，$f_i$就可以通过暴力跳u的fa得到。
这个复杂度和KMP的复杂度类似，都是$O(n)$的。
回到本题，在求出$f_i$后我们实际上就是要对于每个询问求出$lleq ileq r,max{min(f_i , i-l+1)}$的值。
变式一下，令$g_i = i-f_i +1$，则所求为$max{i-min(g_i , l)+1}$。
那么显然可以离线之后以$g_i$为下标建权值线段树，每次在$[0,l-1]$查询$max{i}$，在$[l,n]$查询$max{i-g_i +1}$即可。
如果强制在线，注意到$g_i$是单调不增的，所以可以对于每个$[l,r]$二分一下$g_p leq l$的位置p，然后普通线段树查询即可。
复杂度$O(qlog{n})$。
套路：
- 优化数据结构时：注意维护的信息是否有单调性。
- SAM与AC自动机的异同：都可以解决匹配问题；前者能解决子串，后者只能解决整串。
代码：
#include<bits/stdc++.h> #define maxn 500005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; int F[maxn]; char S[maxn],T[maxn]; vector<int> vec[maxn]; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } struct Ques{int l,r,ans;}Q[maxn]; struct RAMauto{ int to[maxn][30],dis[maxn],fa[maxn]; inline void build(int n){ int tot=1,las=1; for(int i=1;i<=n;i++){ int now=++tot,p=las,ch=T[i]-'a'; dis[tot]=i,las=now; while(p && !to[p][ch]) to[p][ch]=now,p=fa[p]; if(!p) fa[now]=1; else{ int q=to[p][ch]; if(dis[q]==dis[p]+1) fa[now]=q; else{ int nq=++tot; dis[nq]=dis[p]+1; memcpy(to[nq],to[q],sizeof(to[q])); fa[nq]=fa[q],fa[q]=nq,fa[now]=nq; while(p && to[p][ch]==q) to[p][ch]=nq,p=fa[p]; } } } } inline void calc(int n){ int now=1; for(int i=1;i<=n;i++){ int ch=S[i]-'a'; while(now && !to[now][ch]) now=fa[now]; if(!now) now=1,F[i]=0; else F[i]=min(F[i-1],dis[now])+1,now=to[now][ch]; } } }RAM; struct Segmentree{ int mxid[maxn<<2],mxval[maxn<<2]; inline void pushup(int k){ mxid[k]=max(mxid[k<<1],mxid[k<<1|1]); mxval[k]=max(mxval[k<<1],mxval[k<<1|1]); } inline void ins(int x,int y,int l,int r,int k){ if(l==r){mxid[k]=y,mxval[k]=y-x+1;return;} int mid=l+r>>1; if(x<=mid) ins(x,y,l,mid,k<<1); else ins(x,y,mid+1,r,k<<1|1); pushup(k); } inline int qryid(int x,int y,int l,int r,int k){ if(x<=l && r<=y) return mxid[k]; int mid=l+r>>1,res=0; if(x<=mid) res=max(res,qryid(x,y,l,mid,k<<1)); if(y>mid) res=max(res,qryid(x,y,mid+1,r,k<<1|1)); return res; } inline int qryval(int x,int y,int l,int r,int k){ if(x<=l && r<=y) return mxval[k]; int mid=l+r>>1,res=0; if(x<=mid) res=max(res,qryval(x,y,l,mid,k<<1)); if(y>mid) res=max(res,qryval(x,y,mid+1,r,k<<1|1)); return res; } }tr; int main(){ scanf("%s",S+1),scanf("%s",T+1); int n=strlen(S+1),m=strlen(T+1); RAM.build(m),RAM.calc(n); //for(int i=1;i<=n;i++) cout<<F[i]<<" "; //cout<<endl; int q=read(); for(int i=1;i<=q;i++) Q[i].l=read(),Q[i].r=read(),vec[Q[i].r].push_back(i); for(int i=1;i<=n;i++){ int g=i-F[i]+1; tr.ins(g,i,0,n,1); for(int j=0;j<vec[i].size();j++){ int id=vec[i][j],l=Q[id].l; int r1=tr.qryid(0,l-1,0,n,1)-l+1,r2=tr.qryval(l,n,0,n,1); Q[id].ans=max(r1,r2); } } for(int i=1;i<=q;i++) printf("%d ",Q[i].ans); return 0; }