分析

比较综合的题目，这里说几个关键点。

• 反转字符串，前缀变成后缀。

• 二分答案，有单调性。

• 倍增找父亲，线段树上查找 集合是否有 的元素。

• 在 树上线段树合并 + 就做完了。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch=getchar();}
    return f ? -x : x;
  }
  const int N = 4e5 + 190;
  int n,rt[N],pos[N];
  struct SGT {
    int lc[N << 4],rc[N << 4],cnt[N << 4],size;
    void insert(int &u,int l,int r,int pos,int k) {
        if(!u) u=++size;int mid = l + r >> 1;
        cnt[u] += k;if(l == r) return ;
        if(pos <= mid) insert(lc[u],l,mid,pos,k);
        else insert(rc[u],mid + 1,r,pos,k);
    }    
    int merge(int a,int b,int l,int r) {
        if(!a || !b) return a + b;
        int i = ++size;
        cnt[i] = cnt[a] + cnt[b];
        if(l == r) return i;int mid = l + r >> 1;
        lc[i] = merge(lc[a],lc[b],l,mid);
        rc[i] = merge(rc[a],rc[b],mid+1,r);
        return i;
    }
    int query(int u,int l,int r,int L,int R) {
        if(!u) return 0;
        if(L <= l && r <= R) return cnt[u];
        if(l > R || r < L) return 0;
        int mid = l + r >> 1;
        return query(lc[u],l,mid,L,R)+query(rc[u],mid+1,r,L,R);
    }
  }t;
  struct SAM {
    int len[N],fa[N][21],nxt[N][26];
    int last,size;vector<int> G[N];
    void init() {size=last=1;}
    void ins(int c,int pos) {
        int cur=++size;len[cur]=len[last]+1;int p=last;
        t.insert(rt[cur],1,n,pos,1);
        for(;p&&!nxt[p][c];p=fa[p][0])nxt[p][c]=cur;
        if(!p) fa[cur][0] = 1;
        else {
            int q = nxt[p][c];if(len[p]+1==len[q])fa[cur][0]=q;
            else {
                int cl=++size;fa[cl][0]=fa[q][0];len[cl]=len[p]+1;
                for(int i=0;i<26;i++)nxt[cl][i]=nxt[q][i];
                for(;p&&nxt[p][c]==q;p=fa[p][0])nxt[p][c]=cl;
                fa[q][0]=fa[cur][0]=cl;
            }
        }last = cur;
    } 
    void dfs(int x) {
        for(auto y : G[x]) {
            dfs(y);rt[x] = t.merge(rt[x],rt[y],1,n);
        }
    }
    void build() {
        for(int i = 2;i <= size;i++) G[fa[i][0]].push_back(i);
        dfs(1);
        for(int j = 1;j <= 20;j++) {
            for(int i = 1;i <= size;i++) {
                fa[i][j] = fa[fa[i][j-1]][j-1];
            }
        }
    }
    bool check(int limit,int p,int l,int r) {
        for(int i = 20;~i;i--) if(len[fa[p][i]]>=limit&&fa[p][i])p=fa[p][i];
        return t.query(rt[p],1,n,l + limit - 1,r);
    }
  }s;
  int main() {
    static char ch[N];
    n = read();int Q = read();
    scanf("%s",ch + 1);
    reverse(ch + 1,ch + 1 + n);
    s.init();for(int i = 1;i <= n;i++) {
        s.ins(ch[i]-'a',i);pos[i] = s.last;
    }s.build();
    while(Q--) {
        int a = n - read() + 1,b = n - read() + 1,c = n - read() + 1,d = n - read() + 1;
        int r = min(c - d + 1,a - b + 1),l = 0,ans = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(s.check(mid,pos[c],b,a)) l = mid + 1,ans = mid;
            else r = mid - 1;
        }
        printf("%d\n",ans);
    }
  }