题目概述

给出一个字符串 $S$ ，求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。

解题报告

先二分答案 $len$ ，然后只需要验证 $S_{[c,c+len-1]}$ 中是否出现 $[a,b-x+1]$ 后缀。

那么先建出后缀树，然后用DFS序+主席树记录后缀节点是否出现即可。

说一个我刚开始疑惑的问题：就算是深度最浅的包含子串 $[c,c+len-1]$ 的节点也不一定刚好就是 $[c,c+len-1]$ ，那为什么可以在这个节点的子树上查询？其实原因很简单……后缀节点一定不会出现在这条链上……所以查询子树就好了……

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000,maxt=maxn<<1,maxs=1e7,Log=18;

int n,te,A,B,C,D,suf[maxn+5],ti,Lt[maxt+5],Rt[maxt+5],who[maxt+5];char s[maxn+5];
int si=1,fa[maxt+5],MAX[maxt+5],son[maxt+5][26],ID[maxt+5],ST[maxt+5][Log+5];
int len,ro[maxt+5],ls[maxs+5],rs[maxs+5],sum[maxs+5];

namespace SAM{
    int ro=1,p=1,son[maxt+5][26];
    inline void Extend(int w,int i){
        int np=++si;suf[i]=np;ID[np]=i;MAX[np]=MAX[p]+1;while (p&&!son[p][w]) son[p][w]=np,p=fa[p];
        if (!p) fa[np]=ro; else{
            int q=son[p][w];if (MAX[p]+1==MAX[q]) fa[np]=q; else{
                int nq=++si;MAX[nq]=MAX[p]+1;ID[nq]=ID[q];memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[q]=fa[np]=nq;while (p&&son[p][w]==q) son[p][w]=nq,p=fa[p];
            }
        }p=np;
    }
};
void Dfs(int x,int pre=0){
    ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    who[Lt[x]=++ti]=x;for (int i=0;i<26;i++) if (son[x][i]) Dfs(son[x][i],x);Rt[x]=ti;
}
int Build(int l,int r){
    int now=len++;if (l==r) return now;int mid=l+(r-l>>1);
    ls[now]=Build(l,mid);rs[now]=Build(mid+1,r);return now;
}
#define Pushup(p) (sum[p]=sum[ls[p]]+sum[rs[p]])
int Insert(int p,int pos,int k,int l=1,int r=n){
    int now=len++;ls[now]=ls[p];rs[now]=rs[p];sum[now]=sum[p];if (l==r) return sum[now]+=k,now;int mid=l+(r-l>>1);
    pos<=mid?ls[now]=Insert(ls[p],pos,k,l,mid):rs[now]=Insert(rs[p],pos,k,mid+1,r);return Pushup(now),now;
}
inline void MakeST(){
    for (int i=2;i<=si;i++) son[fa[i]][s[ID[i]+MAX[fa[i]]]-'a']=i;Dfs(1);
    ro[0]=Build(1,n);for (int i=1;i<=si;i++) ID[who[i]]?ro[i]=Insert(ro[i-1],ID[who[i]],1):ro[i]=ro[i-1];
}
int Ask(int A,int B,int L,int R,int l=1,int r=n){
    if (R<l||r<L) return 0;if (L<=l&&r<=R) return sum[B]-sum[A];int mid=l+(r-l>>1);
    return Ask(ls[A],ls[B],L,R,l,mid)+Ask(rs[A],rs[B],L,R,mid+1,r);
}
inline bool check(int len){
    int L=suf[C];for (int j=Log;~j;j--) if (MAX[ST[L][j]]>=len) L=ST[L][j];
    return Ask(ro[Lt[L]-1],ro[Rt[L]],A,B-len+1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%s",&n,&te,s+1);for (int i=n;i;i--) SAM::Extend(s[i]-'a',i);
    for (MakeST();te;te--){
        scanf("%d%d%d%d",&A,&B,&C,&D);int L=1,R=min(B-A+1,D-C+1);
        for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) check(mid)?L=mid+1:R=mid-1;printf("%d\n",R);
    }
    return 0;
}