感觉这个 $T3$ 没 $T2$ 难？
显然是 $SAorSAM$ 。而 $SA$ 虽然码量高但是更好想。
考虑 $SA$ 维护 $f_i$ 表示 $S$ 串的 $suf_i$ 与 $T$ 串的最大长度。可以直接通过 $height$ 数组求得。
则询问 $[l,r]$ 的答案可以写为 $max{min{f_i,r-i+1}}$ 。显然是可以主席树维护的，但是可以通过按照 $r$ 排序使用两个线段树维护 $f_i$ 与 $-i+1$ 是否成立。
时间复杂度 $O(nlog n)$ 。
#include<iostream> #include<cstring> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<algorithm> #include<climits> #include<bitset> #include<set> #define pii pair<int,int> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=4e5+11; char S[MAXN],T[MAXN],str[MAXN]; int N,M,len,ht[MAXN],buc[MAXN],rnk[MAXN],sa[MAXN],tp[MAXN],MM=140,Log[MAXN],INF; struct Segment{ int Maxn[MAXN<<2]; void clear(){memset(Maxn,-127/3,sizeof(Maxn));INF=Maxn[0];} void Modify(int k,int l,int r,int ps,int w){ if(l==r){Maxn[k]=w;return;} int mid=(l+r)>>1; if(ps<=mid) Modify(k<<1,l,mid,ps,w); else Modify(k<<1|1,mid+1,r,ps,w); Maxn[k]=max(Maxn[k<<1],Maxn[k<<1|1]);return; } int Query(int k,int l,int r,int x,int y){ if(x<=l&&r<=y)return Maxn[k]; int mid=(l+r)>>1,res=INF; if(x<=mid) res=max(res,Query(k<<1,l,mid,x,y)); if(mid<y) res=max(res,Query(k<<1|1,mid+1,r,x,y)); return res; } }SS,TT; int Ans[MAXN]; vector<int> s[MAXN];int cnt[MAXN]; pii ff[MAXN]; struct Union{ int f[MAXN]; int find(int x){return f[x]==x?x:f[x]=find(f[x]);} void init(){for(int i=1;i<=len;i++) f[i]=i;} void merge(int x1,int x2,int w){ int t1=find(x1),t2=find(x2);f[t2]=t1; if(s[t2].size()&&cnt[t1]){for(auto v:s[t2]) Ans[v]=w;s[t2].clear();} if(s[t1].size()&&cnt[t2]){for(auto v:s[t1]) Ans[v]=w;s[t1].clear();} for(auto v:s[t2]) s[t1].pb(v); cnt[t1]+=cnt[t2];return; } }U; int Q,An[MAXN]; vector<pii> vec[MAXN],que[MAXN]; int main(){ scanf("%s%s",S+1,T+1);N=strlen(S+1),M=strlen(T+1);Log[0]=-1;for(int i=1;i<=N;i++) Log[i]=Log[i>>1]+1; for(int i=1;i<=M;i++) str[++len]=T[i];str[++len]='&';for(int i=1;i<=N;i++) str[++len]=S[i]; for(int i=1;i<=len;i++) buc[rnk[i]=str[i]]++; for(int i=0;i<=MM;i++) buc[i]+=buc[i-1]; for(int i=len;i>=1;i--) sa[buc[rnk[i]]--]=i; for(int k=1;k<=len;k<<=1){ for(int i=0;i<=MM;i++) buc[i]=0; int p=0;for(int i=len-k+1;i<=len;i++) tp[++p]=i; for(int i=1;i<=len;i++) if(sa[i]>k) tp[++p]=sa[i]-k; for(int i=1;i<=len;i++) buc[rnk[i]]++; for(int i=1;i<=MM;i++) buc[i]+=buc[i-1]; for(int i=len;i>=1;i--) sa[buc[rnk[tp[i]]]--]=tp[i]; swap(rnk,tp);p=1;rnk[sa[1]]=1; for(int i=2;i<=len;i++) rnk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p; MM=p; } for(int i=1,k=0;i<=len;i++){ if(k) k--; while(str[i+k]==str[sa[rnk[i]-1]+k]) k++; ht[rnk[i]]=k; } for(int i=1;i<=len;i++) ff[i]=mp(-ht[i],i);sort(ff+1,ff+len+1); for(int i=1;i<=M;i++) cnt[rnk[i]]=1; for(int i=1;i<=N;i++) s[rnk[M+i+1]].pb(i); U.init(); for(int i=1;i<len;i++){ int l=ff[i].se-1,r=ff[i].se; U.merge(l,r,-ff[i].fi); }Q=read(); for(int i=1;i<=Q;i++){int l=read(),r=read();que[r].pb(mp(l,i));} SS.clear(),TT.clear(); for(int i=1;i<=N;i++) vec[Ans[i]+i-1].pb(mp(i,Ans[i])),SS.Modify(1,1,N,i,-i+1); for(int i=1;i<=N;i++){ for(auto v:vec[i]){ SS.Modify(1,1,N,v.fi,INF),TT.Modify(1,1,N,v.fi,v.se); } for(auto v:que[i]){ int l=v.fi,r=i,id=v.se; An[id]=max(SS.Query(1,1,N,l,r)+r,TT.Query(1,1,N,l,r)); } } for(int i=1;i<=Q;i++) printf("%d ",An[i]); return 0; }/* abababbaa bbbaab 1 1 3 */