Border 的第六种求法

Moeebius · 2026-02-13 20:22:30 · 算法·理论

tl;dr: 本文给出了一种在不借助任何 Border 理论，只需要后缀树的做法，这一做法可以在 O(n \log n) 时间复杂度内预处理并在 O(\log n) 时间复杂度内在线求解原串的某个子串 S[L, R] 中，长度在某个区间 [l, r] 内的最长 / 最短 Border。

文末将给出一份 luogu P4482 的 O((n+q) \log n) 的参考实现。

这一做法是笔者某天晚上自己想出来的，不确定是否有前人提出过类似的做法。不过笔者翻阅了 P4482 的题解区，发现只有 @lzyqwq 的题解可能使用了类似的思路，不过他并没有将其优化到 1 log。

O(n \log^2 n) - O(\log^2 n)

方便起见，下文使用的后缀数据结构为 SAM，事实上我们只用到了 SAM 的 parent 树结构，因此将 SAM 替换成后缀树应当也是可行的。

首先考虑一个弱化版问题：如何判断某个子串是否存在一个长度非 0 的 border？

一个简单的想法是分块。注意到 check 某个长度的 border 存不存在是简单的，我们只需要在 parent 树上 query 两个点的 LCA 看一下 LCS 够不够长即可。这里暴力可以做到 O(n \log n) - O(1)。而对于整块，我们考虑对 parent 树上每个点 p 求出其子树内最小的落在这个整块内的 endpos f_p，那么对于一组询问我们相当于就是要 check 某条到根链上是否存在一个点 i 满足 f_i - len_i + 1 \le L，扫一遍整棵树预处理即可。复杂度 O(n \sqrt n)，可能需要离线避免空间上带个根号。

不过事实上，我们可以把这个问题做到 polylog。注意到扫一遍整棵树非常浪费，考虑对关键点建虚树。我们建一棵线段树，对每个线段树节点 [l, r] 建出一棵 parent 树上，\{S[1,l],S[1,l+1],\cdots,S[1,r]\} 这些子串对应节点的虚树。对于查询操作，本质上就是我需要从某个点往上跳父亲，直到跳到一个子树内存在虚树中节点的点 p：这时可能贡献到 \min\{f_i - len_i + 1\} 的有两类点，一类是 i=p，另一类是 i 在 \text{fa}_p 到根链上。我们可以找出 p 子树内，在虚树上的深度最浅的点 q（容易证明 q 唯一），对于第一类显然有 f_i = f_q，对于第二类，我们预处理虚树上每个点到根链上的最小权值 g_i，查询 q 在虚树上父亲 r 的 g_r 即可。找 p,q 均可以使用二分 / LCA 等实现，在单个线段树节点上进行一次询问的复杂度不会超过 O(\log n)。由于每个区间在线段树上会被拆到 O(\log n) 个节点，询问复杂度 O(\log^2 n)。对于预处理，暴力的做法是对每个线段树节点两次 sort 建虚树，复杂度 O(n \log ^ 2 n)。

回到原问题。虽然 border 本身不具有可二分性，但是我们可以 check 某个长度区间里有没有 border，因此我们直接在上述做法上套个线段树二分就能以同样的复杂度解决原问题。

笔者尚未仔细阅读 @lzyqwq 的题解，不过考虑到他用的是 SA，很可能使用了类似的做法，但比较难进一步优化。

O(n \log n) - O(\log n)

还能再给力一点吗？

首先预处理很好优化：我们使用只需要 sort 关键点一次的虚树建法，同时发现线段树每个节点对应的关键点一定是其两个儿子的无交并，因此改归并即可。

对于询问，肯定不能在每个线段树节点内分别二分，考虑利用线段树作为分治结构的性质，类似分散层叠的思路，假如我们可以根据在某个线段树节点 a 上定位到的 q 求出在 \text{lc}(a)，\text{rc}(a) 上定位到的 q', q''，我们就可以通过直接求一次 LCA 还原出来 p', p''，从而知道所有需要的信息。

这是可以在预处理阶段完成的。注意到，假如 S \subseteq T，那么对于 S,T 作为关键点集求出的虚树 vt(S), vt(T) 一定有 vt(S) \subseteq vt(T)。

有以下关键结论：记在虚树 T 上，点 k 按照上述规则定位到的点 q 为 to_T(k)，且 S \subset T，则 to_S(k) = to_S(to_T(k))。

证明：

• 记在虚树 T 上定位到的点 p（即 \text{LCA}(q, k)）为 h_T(k)；记点 k 子树内的点集（不一定要在虚树上）为 st(k)。
• 由 p, q 定义，在虚树 T 上，st(h_T(k)) \setminus st(to_T(k)) 内一定没有 T 上的点，显然也没有 S 中的点。
• 如果 st(to_T(k)) \cap S \neq \empty，那么求 to_S(k) 和 to_S(to_T(k)) 的时候，都会在 to_T(k) 子树内找到在 S 中且深度最浅的唯一点，结论正确。
• 否则，h_S(k) 是 h_T(k) 的祖先，又因为 st(h_T(k)) \cap S = \empty，无论是求 to_S(to_T(k)) 还是求 to_S(k)，在第一步（即往上跳父亲直到子树内存在虚树中点）时都会至少跳到 h_T(k) 的父亲，相当于两者可以认为是从同一个起点开始跳的，自然相同。\square

而又因为 to_T(k) 显然在 T 上，我们只需要预处理出虚树上每个点 k，在线段树左右儿子的虚树 S 上的 to_S(k) 就行了，这是好做的。

综上，我们在 O(n \log n) - O(\log n) 时间复杂度内解决了这一问题。

参考实现

题目为 luogu P4482。

#include <bits/stdc++.h>

using namespace std;

// #define USE_INT_128

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define $0 get<0>
#define $1 get<1>
#define $2 get<2>
#define $3 get<3>
#define $4 get<4>
#define ssz(x) (signed((x).size()))
#define beg2ed(x) (x).begin(), (x).end()
#define _loop_i_t(j, k) make_signed_t<decltype((j) - (k))>
#define For(i, j, k) for (_loop_i_t(j, k) i = (j); i <= (k); ++i)
#define ForDown(i, j, k) for (_loop_i_t(j, k) i = (j); i >= decltype(i)(k); --i)
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
constexpr il ll qpow(ll x, ull y, ll mod){ ll ans = 1; x %= mod; while (y) { if (y & 1) (ans *= x) %= mod; (x *= x) %= mod; y >>= 1; } return ans; }
template<typename T> constexpr il void cmin(T &x, const T &y){ x = min(x, y); }
template<typename T> constexpr il void cmax(T &x, const T &y){ x = max(x, y); }
// clang-format on

// File head end

namespace {
constexpr int MAXN = 2e5 + 5;

struct SAM {
  struct Node {
    int fa, len, nxt[26];
    Node() : fa(-1), len(0) { memset(nxt, -1, sizeof nxt); }
  } sam[MAXN << 1];
  int lst, cnt, id[MAXN], dep[MAXN << 1], dfn[MAXN << 1], seq[19][MAXN << 1],
      sz[MAXN << 1];
  vector<int> tr[MAXN << 1];
  SAM() : lst(0), cnt(1) {}
  template <typename _InputIt> SAM(_InputIt st, _InputIt ed) : lst(0), cnt(1) {
    for (auto [it, i] = mkp(st, 1); it != ed; ++it, ++i)
      ins(*it), id[i] = lst;
    build();
  }
  void ins(char ch) {
    int c = ch - 'a', p = lst;
    sam[lst = cnt++].len = sam[p].len + 1;
    while (~p && !~sam[p].nxt[c])
      sam[p].nxt[c] = lst, p = sam[p].fa;
    if (!~p)
      return sam[lst].fa = 0, void();
    int q = sam[p].nxt[c];
    if (sam[q].len == sam[p].len + 1)
      sam[lst].fa = q;
    else {
      int clone = cnt++;
      sam[clone] = sam[q], sam[clone].len = sam[p].len + 1;
      sam[q].fa = sam[lst].fa = clone;
      while (~p && sam[p].nxt[c] == q)
        sam[p].nxt[c] = clone, p = sam[p].fa;
    }
  }
  void build() {
    For(i, 1, cnt - 1) tr[sam[i].fa].eb(i);
    int tot = 0;
    auto dfs = [&](auto &&dfs, int x) -> void {
      seq[0][dfn[x] = tot++] = x, dep[x] = !x ? 0 : (dep[sam[x].fa] + 1);
      sz[x] = 1;
      for (int v : tr[x])
        dfs(dfs, v), sz[x] += sz[v];
    };
    dfs(dfs, 0), assert(tot == cnt);
    For(i, 1, 18) For(j, 0, tot - (1 << i)) {
      int u = seq[i - 1][j], v = seq[i - 1][j + (1 << (i - 1))];
      seq[i][j] = dep[u] < dep[v] ? u : v;
    }
  }
  int LCA(int x, int y) const {
    if (x == y)
      return x;
    auto [l, r] = minmax(dfn[x], dfn[y]);
    int f = 31 ^ __builtin_clz(r - l), u = seq[f][l + 1],
        v = seq[f][r - (1 << f) + 1];
    return sam[dep[u] < dep[v] ? u : v].fa;
  }
  int LCS(int x, int y) const { return sam[LCA(id[x], id[y])].len; }
} A;

int n, q;
string str;

vector<pii> key[MAXN << 2];
vector<tuple<int, int, int, int, pii>> vec[MAXN << 2];
#define lc(p) ((p) << 1)
#define rc(p) ((p) << 1 | 1)
int _id[MAXN << 1], _ch[MAXN << 1][2], _minv[MAXN << 1];
pii _tmp[MAXN << 1];
vector<int> _tr[MAXN << 1];
void build(int P, int l, int r) {
  if (l != r) {
    int mid = (l + r) >> 1;
    build(lc(P), l, mid), build(rc(P), mid + 1, r);
    key[P].resize(ssz(key[lc(P)]) + ssz(key[rc(P)]));
    merge(beg2ed(key[lc(P)]), beg2ed(key[rc(P)]), key[P].begin());
    key[P].erase(unique(beg2ed(key[P])), key[P].end());
    vector<pii>{}.swap(key[lc(P)]), vector<pii>{}.swap(key[rc(P)]);
  } else
    key[P] = {{A.dfn[A.id[l]], A.id[l]}};

  auto init = [&](int x) {
    _tr[x].clear(), _ch[x][0] = _ch[x][1] = -1, _minv[x] = 0x3f3f3f3f;
  };
  auto &vec = ::vec[P];
  int len = ssz(key[P]) + 1;
  vector<int> st{0};
  init(0);
  assert(is_sorted(beg2ed(key[P])));
  for (auto [_, x] : key[P]) {
    int lca = A.LCA(st.back(), x);
    if (lca != st.back()) {
      int d = A.dep[lca];
      while (ssz(st) > 1 && A.dep[st.end()[-2]] >= d)
        _tr[st.end()[-2]].eb(st.back()), st.pop_back();
      if (st.back() != lca)
        assert(ssz(st) > 1), len++, init(lca), _tr[lca].eb(st.back()),
            st.back() = lca;
    }
    init(x), st.eb(x);
  }
  For(i, 1, ssz(st) - 1) _tr[st[i - 1]].eb(st[i]);

  memset(_tmp, -1, len * sizeof(pii));
  For(i, l, r) _minv[A.id[i]] = i;

  if (l != r) {
    int pos = 0;
    for (const auto &x : ::vec[lc(P)])
      _ch[$0(x)][0] = pos++;
    pos = 0;
    for (const auto &x : ::vec[rc(P)])
      _ch[$0(x)][1] = pos++;
  }

  auto dfs1 = [&](auto &&dfs, int x, int pre) -> void {
    int p = (_id[x] = ssz(vec));
    vec.eb(x, 0x3f3f3f3f, 0x3f3f3f3f, pre, pii{0, 0});
    if (~_ch[x][0])
      _tmp[p].fi = _ch[x][0];
    if (~_ch[x][1])
      _tmp[p].se = _ch[x][1];
    for (int v : _tr[x]) {
      dfs(dfs, v, p);
      int q = _id[v];
      if (!~_tmp[p].fi && ~_tmp[q].fi)
        _tmp[p].fi = _tmp[q].fi;
      if (!~_tmp[p].se && ~_tmp[q].se)
        _tmp[p].se = _tmp[q].se;
      cmin(_minv[x], _minv[v]);
    }
    $1(vec[p]) = _minv[x];
  };
  dfs1(dfs1, 0, -1), assert(len == ssz(vec));
  $4(vec[0]) = _tmp[0], $2(vec[0]) = l + 1;
  For(i, 1, len - 1) {
    int fa = $3(vec[i]);
    assert(fa >= 0 && fa < i);
    $2(vec[i]) = min($2(vec[fa]), $1(vec[i]) - A.sam[$0(vec[i])].len + 1);
    $4(vec[i]).fi = ~_tmp[i].fi ? _tmp[i].fi : $4(vec[fa]).fi;
    $4(vec[i]).se = ~_tmp[i].se ? _tmp[i].se : $4(vec[fa]).se;
  }
}
bool chk(int p, int id, int pos, int lim) {
  assert(id >= 0 && id < ssz(vec[p]));
  int q = A.id[pos];
  const auto &o = vec[p][id];
  return min($1(o) - A.sam[A.LCA(q, $0(vec[p][id]))].len + 1,
             ~$3(o) ? $2(vec[p][$3(o)]) : 0x3f3f3f3f) <= lim;
}

int qry(int p, int l, int r, int ql, int qr, int id) {
  if (ql <= l && qr >= r && !chk(p, id, qr + 1, ql))
    return 0;
  if (l == r)
    return l - ql + 1;
  int mid = (l + r) >> 1, ans = 0;
  if (qr > mid && (ans = qry(rc(p), mid + 1, r, ql, qr, $4(vec[p][id]).se)))
    return ans;
  if (ql <= mid && (ans = qry(lc(p), l, mid, ql, qr, $4(vec[p][id]).fi)))
    return ans;
  return 0;
}

void Main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> str >> q, n = str.length();
  new (&A) SAM(str.begin(), str.end());
  build(1, 1, n);
  while (q--) {
    int l, r;
    cin >> l >> r;
    assert(~_id[A.id[r]] && _id[A.id[r]] < ssz(vec[1]) &&
           $0(vec[1][_id[A.id[r]]]) == A.id[r]);
    cout << qry(1, 1, n, l, r - 1, _id[A.id[r]]) << '\n';
  }
}
} // namespace

signed main() { return Main(), 0; }