P4094

题目大意

给你一个字符串 $S$，有 $q$ 次询问。

每次询问给出四个数 $a$，$b$，$c$，$d$。

求 $\max_{a\le l\le r\le b}lcp(S[l\ldots r],S[c\ldots d])$。

后缀数组

解题思路

先二分答案，令长度为 $mid$ ，接下来就是要判断是否存在 $a\le pos\le b-mid+1$ 使 $S[pos\ldots pos+mid-1]=S[c\ldots c+mid-1]$。

也就是说 $lcp(S[pos\ldots n],S[c\ldots n])\ge mid$。

注意到若不关心 $pos$ 的范围，那么 $pos$ 在 $SA$ 上一定是连续的一段，可以用二分得到范围，再判断一下区间内是否出现了 $[a,b-mid+1]$ 中的数即可。

用主席树维护即可。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define fin(s) freopen(s, "r", stdin)
#define fout(s) freopen(s, "w", stdout)
#define fio(s) fin(s".in"), fout(s".out")
using ll = long long; using ull = uint64_t;
using lll = __int128; using ulll = __uint128_t;
using db = double; using ldb = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vl = vector<ll>;
using uid = uniform_int_distribution<ll>;
using urd = uniform_real_distribution<db>;
#define rep(i, a, b) for(auto i = (a); i <= (b); i++)
#define per(i, a, b) for(auto i = (a); i >= (b); i--)
#define Edge(i, h, e, x) for(int i = h[x]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
#define Size(a) ((int)(a).size())
#define mem(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))

mt19937 rnd(random_device{}());
const ll mod = 998244353;

struct SuffixSort{
  static const int N = 1e5 + 10;
  int sa[N], tp[N], tax[N], rnk[N], tot, n, m, h[N];
  char s[N];
  void sort() {
    fill(tax, tax + 1 + m, 0);
    rep(i, 1, n) tax[rnk[i]]++;
    rep(i, 1, m) tax[i] += tax[i - 1];
    per(i, n, 1) sa[tax[rnk[tp[i]]]--] = tp[i];
  }
  void init(const char *_s, int _n) {
    n = _n, m = 0xff;
    memcpy(s + 1, _s + 1, n);
    rep(i, 1, n) tp[i] = i, rnk[i] = s[i]; sort();
    for(int l = 1; tot < n; l <<= 1, m = tot) {
      tot = 0;
      rep(i, 1, l) tp[++tot] = n - l + i;
      rep(i, 1, n) if(sa[i] > l) tp[++tot] = sa[i] - l;
      sort(); swap(tp, rnk); rnk[sa[1]] = tot = 1;
      rep(i, 2, n)
        if(tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + l] == tp[sa[i - 1] + l]) rnk[sa[i]] = tot;
        else rnk[sa[i]] = ++tot;
    }
    rep(i, 1, n) rnk[sa[i]] = i;
    int k = 0;
    rep(i, 1, n) {
      if(rnk[i] == 1) continue;
      k -= !!k;
      int j = sa[rnk[i] - 1];
      for(; i + k <= n && j + k <= n && s[i + k] == s[j + k]; k++);
      h[rnk[i]] = k;
    }
  }
} SA;

struct RMQ {
  static const int N = 1e5 + 10, K = 30, inf = 1e9;
  int st[N][K], n, a[N];
  void init(int *_a, int _n) {
    n = _n;
    rep(i, 1, n) a[i] = _a[i];
    rep(i, 1, n) rep(j, 0, K - 1) st[i][j] = inf;
    rep(i, 1, n) st[i][0] = a[i];
    rep(j, 1, K - 1) rep(i, 1, n - (1 << j) + 1)
      st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
  }
  int qry(int l, int r) {
    int len = __lg(r - l + 1);
    return min(st[l][len], st[r - (1 << len) + 1][len]);
  }
} ST;

struct PresidentTree {
  static const int N = 1e5 + 10, K = 30;
  int a[N], n, rt[N], ch[N * K][2], t[N * K], tot = 0;
  #define lcx ch[x][0]
  #define rcx ch[x][1]
  #define lcy ch[y][0]
  #define rcy ch[y][1]
  #define mid (l + r >> 1)
  void up(int x) { t[x] = t[lcx] + t[rcx]; }
  void upd(int &x, int y, int l, int r, int p, int v) {
    if(p > r || p < l) { x = y; return; }
    if(!x) x = ++tot;
    if(l == r) { t[x] = t[y] + v; return; }
    upd(lcx, lcy, l, mid, p, v);
    upd(rcx, rcy, mid + 1, r, p, v);
    up(x);
  }
  int qry(int x, int y, int l, int r, int a, int b) {
    if(l > b || a > r || !y) return 0;
    if(a <= l && r <= b) return t[y] - t[x];
    return qry(lcx, lcy, l, mid, a, b) + qry(rcx, rcy, mid + 1, r, a, b);
  }
  void init(int *_a, int _n) {
    n = _n;
    rep(i, 1, n) a[i] = _a[i];
    rep(i, 1, n) upd(rt[i], rt[i - 1], 1, n, a[i], 1);
  }
  #undef lcx
  #undef lcy
  #undef rcx
  #undef rcy
  #undef mid
} SGT;

const int N = 1e5 + 10;
int n, m;
char s[N];

int getT1(int x, int len) {
  int l = 1, r = x;
  for(; l < r; ) {
    int mid = l + r >> 1;
    if(ST.qry(mid + 1, x) >= len) r = mid;
    else l = mid + 1;
  }
  return l;
}
int getT2(int x, int len) {
  int l = x, r = n;
  for(; l < r; ) {
    int mid = l + r + 1 >> 1;
    if(ST.qry(x + 1, mid) >= len) l = mid;
    else r = mid - 1;
  }
  return l;
}

bool check(int a, int b, int x, int len) {
  int t1 = getT1(x, len), t2 = getT2(x, len);
  return SGT.qry(SGT.rt[a - 1], SGT.rt[b], 1, n, t1, t2);
}

void solve(int a, int b, int c, int d) {
  int l = 0, r = min(b - a + 1, d - c + 1);
  for(; l < r; ) {
    int mid = l + r + 1 >> 1;
    if(check(a, b - mid + 1, SA.rnk[c], mid)) l = mid;
    else r = mid - 1;
  }
  printf("%d\n", l);
}

int main() {
  scanf("%d%d%s", &n, &m, s + 1);
  SA.init(s, n);
  ST.init(SA.h, n);
  SGT.init(SA.rnk, n);
  for(; m--; ) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    solve(a, b, c, d);
  }
}

后缀自动机

解题思路

还是先二分答案，令答案为 $mid$。
此时我们需要判断是否存在一个 $a+mid-1\le pos\le b$ 使 $S[pos-mid+1\ldots pos]=S[c\ldots c+mid-1]$。
也就是 $S[c\ldots c+mid-1]$ 是 $S[1\ldots pos]$ 的后缀。
在 $SAM$ 上就是说 $S[c\ldots c+mid-1]$ 所在的 $endpos$ 等价类包含了一个 $pos$ 满足 $a+mid-1\le pos\le b$。
我们可以先在 $Parent\ Tree$ 倍增出 $S[c\ldots c+mid-1]$ 所在的 $endpos$ 等价类，然后用值域线段树合并来判断是否可行。

代码实现

在代码里我使用了 $3$ 倍的倍增，实测比 $2$ 倍的快了 $3$ 秒多。

#include<bits/stdc++.h>
using namespace std;
#define fin(s) freopen(s, "r", stdin)
#define fout(s) freopen(s, "w", stdout)
#define fio(s) fin(s".in"), fout(s".out")
using ll = long long; using ull = uint64_t;
using lll = __int128; using ulll = __uint128_t;
using db = double; using ldb = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vl = vector<ll>;
template<class T> using uid = uniform_int_distribution<T>;
template<class T> using urd = uniform_real_distribution<T>;
#define rep(i, a, b) for(auto i = (a); i <= (b); i++)
#define per(i, a, b) for(auto i = (a); i >= (b); i--)
#define go(i, h, e, x) for(int i = h[x]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define getsz(a) ((int)(a).size())
#define mem(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))

mt19937 rnd(random_device{}());
const ll mod = 998244353;

namespace SegmentTreeSpace {
  const int N = 2e5 + 10, K = 60;
  #define lcx ch[x][0]
  #define lcy ch[y][0]
  #define rcx ch[x][1]
  #define rcy ch[y][1]
  #define mid (l + r >> 1)
  int ch[N * K][2], t[N * K], tot, n;
  void up(int x) { t[x] = t[lcx] + t[rcx]; }
  void update(int &x, int l, int r, int p, int v) {
    if(p > r || p < l) return;
    if(!x) x = ++tot;
    if(l == r) { t[x] += v; return; }
    update(lcx, l, mid, p, v), update(rcx, mid + 1, r, p, v), up(x);
  }
  int merge(int x, int y, int l, int r) {
    if(!x || !y) return x | y;
    int z = ++tot;
    if(l == r) { t[z] = t[x] + t[y]; return z; }
    ch[z][0] = merge(lcx, lcy, l, mid);
    ch[z][1] = merge(rcx, rcy, mid + 1, r);
    up(z); return z;
  }
  int query(int x, int l, int r, int a, int b) {
    if(l > b || a > r || !x) return 0;
    if(a <= l && r <= b) return t[x];
    return query(lcx, l, mid, a, b) + query(rcx, mid + 1, r, a, b);
  }
  #undef lcx
  #undef lcy
  #undef rcx
  #undef rcy
  #undef mid
}

struct SegmentTree {
  int id = 0;
  SegmentTree() {}
  SegmentTree(int id): id(id) {}
  void update(int p, int v) {
    SegmentTreeSpace::update(
      id,
      1, SegmentTreeSpace::n,
      p, v
    );
  }
  int query(int a, int b) {
    return SegmentTreeSpace::query(
      id,
      1, SegmentTreeSpace::n,
      a, b
    );
  }
  friend SegmentTree merge(SegmentTree x, SegmentTree y) {
    return SegmentTree(
      SegmentTreeSpace::merge(
        x.id, y.id,
        1, SegmentTreeSpace::n
      )
    );
  }
};

struct SAM{
  static const int N = 2e5 + 10, K = 26, LOGN = 13;
  int len[N], fa[N], lst = 1, tot = 1;
  int ch[N][K], n;
  int anc[N][LOGN], id[N];
  char s[N];
  SegmentTree sgt[N];
  vi ed[N];
  void insert(int c) {
    int f = lst, x = lst = ++tot;
    len[x] = len[f] + 1;
    for(; f && !ch[f][c]; f = fa[f]) ch[f][c] = x;
    if(!f) { fa[x] = 1; return; }
    if(len[ch[f][c]] == len[f] + 1) { fa[x] = ch[f][c]; return; }
    int w = ch[f][c], q = ++tot;
    len[q] = len[f] + 1, fa[q] = fa[w], fa[w] = fa[x] = q;
    mcpy(ch[q], ch[w]);
    for(; f && ch[f][c] == w; f = fa[f]) ch[f][c] = q;
  }
  void dfs(int x) {
    rep(i, 1, LOGN - 1) anc[x][i] = anc[anc[anc[x][i - 1]][i - 1]][i - 1];
    for(int y: ed[x]) {
      anc[y][0] = x;
      dfs(y);
      sgt[x] = merge(sgt[x], sgt[y]);
    }
  }
  void build(const char *_s, int _n) {
    n = _n; memcpy(s + 1, _s + 1, n);
    rep(i, 1, n) insert(s[i] - 'a'), sgt[lst].update(i, 1), id[i] = lst;
    rep(i, 1, tot) ed[fa[i]].pb(i);
    dfs(1);
  }
  int findnode(int mid, int l) {
    int x = id[mid];
    per(i, LOGN - 1, 0) {
      if(len[anc[x][i]] >= l) x = anc[x][i];
      if(len[anc[x][i]] >= l) x = anc[x][i];
    }
    return x;
  }
} g;

const int N = 1e5 + 10;
char s[N];
int n, q;

bool check(int mid, int l, int left, int right) {
  return g.sgt[g.findnode(mid, l)].query(left, right);
}

int solve(int a, int b, int c, int d) {
  int l = c - 1, r = min(d, c + (b - a + 1) - 1);
  for(; l < r; ) {
    int mid = l + r + 1 >> 1;
    if(check(mid, mid - c + 1, a + (mid - c + 1) - 1, b)) l = mid;
    else r = mid - 1;
  }
  return l - c + 1;
}

int main() {
  scanf("%d%d", &n, &q);
  SegmentTreeSpace::n = n;
  scanf("%s", s + 1);
  g.build(s, n);
  for(; q--; ) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    printf("%d\n", solve(a, b, c, d));
  }
}