后缀数组学习笔记

lzyqwq · 2023-10-13 10:53:10 · 算法·理论

cnblogs

前言

后缀数组（Suffix Array，简称 SA）是一种解决某些字符串问题的常用工具。解决这些字符串问题时，经常用后缀数组对问题进行一定的转化成其它的模型，然后套用那个模型的解决方法加以解决原问题。

附题单

约定

本文做以下约定：

• 本文撰写时间跨度较大，有些符号会出现正体、斜体混用的情况，请读者甄别。

• 记 \Sigma 为字符集。具体的字符（串）使用⌈打印机字体⌋表示，如 \texttt{lzyqwq}。用 |s| 表示字符串 s 的长度。本文中字符串的下标从 \boldsymbol 1 开始，代码中视实现方便程度可能会有所差异。

• 记 \overline{c_1c_2\dots c_k} 表示字符 c_1\sim c_k 从左往右依次拼接形成的字符串。记 s_i 为字符串 s 从左至右的第 i 个字符。若 i>|s|，则认为它为空字符。

• 记 \text{LCP}(s,t) 为字符串 s,t 的最长公共前缀。形式化地，|\text{LCP}(s,t)|=l，当且仅当 \nexists\,j\in[1,l],s_j\ne t_j 且 s_{l+1}\ne t_{l+1}。下文有时会简称为 \text{LCP}。

• 称一个字符串 s 的字典序比字符串 t 小，记 |\text{LCP}(s,t)|=l，当且仅当 \nexists \, j\in[1,l],s_j \ne t_j 且 s_{l+1}<t_{l+1}。认为空字符的字典序极小。

• 记 s[l,r] 为字符串 s 删去前 l-1 个字母和后 |s|-r 个字母得到的字符串，称其为字符串 s 从 l 到 r 的子串。形式化地，s[l,r]=\overline{s_ls_{l+1}\dots s_r}。显然，s[1,i] 为字符串 s 的一个前缀，s[i,|s|] 为字符串 s 的一个后缀。

• 对于字符串 s，记 pre_i=s[1,i]，suf_i=s[i,|s|]。

• 记 rk_i 表示将字符串 s 的所有后缀按照字典序从小到大排序后，后缀 s[i,|s|] 的排在第几位。称为后缀 s[i,|s|] 的排名。

• 记 sa_i 表示排名为 i 的后缀的起始位置。形式化地，若 sa_i=j，则 rk_j=i，即 sa_{rk_i}=i。

构建

后缀数组最初被用来解决这样一个问题：

P3809 【模板】后缀排序

• 给出一个字符串 s，对于 i\in[1,|s|]，求 sa_i。

表面上这题要求我们求 sa_i，其实我们可以求出 rk_i，然后根据 sa_{rk_i}=i 求出 sa_i。即我们需要对所有后缀进行排序。

【方法一：取出所有后缀并进行排序】

这就是最暴力求解后缀数组的方法，时间复杂度为 \mathcal{O}(|s|^2\log |s|)，空间复杂度为 \mathcal{O}(|s|^2)。

提交记录（UNAC 45pts）

代码

【方法二：字符串哈希加速比较】

方法一的效率主要低在比较两个字符串的大小。根据前文对字典序的定义，我们可以用二分 + 字符串哈希找到两个后缀的 \text{LCP}，然后比较下一位字符。

这样一来，单次比较的时间复杂度为 \mathcal{O}(\log|s|)，总时间复杂度为 \mathcal{O}(|s|\log ^2 |s|)，空间复杂度为 \mathcal{O}(|s|)。

提交记录（卡常后 AC）

代码

【方法三：倍增法】

考虑将 s 的所有后缀的长度用空字符补齐至长度为 |s| 后，再用空字符继续补齐为 2^{\lfloor\log_2|s|\rfloor+1}，显然后缀之间的大小关系不变。

问题转化为，将以某个位置开头，长度为 2^{\lfloor\log_2|s|\rfloor+1} 的用空字符补齐后的字符串排序。

设 str(p)_i 表示以 i 为开头，长度为 2^p 的用空字符补齐后的字符串，rk(p)_i 为其排名。那么 rk(0) 就是单个字符之间的比较，容易求得。考虑如何用 rk(p) 求得 rk(p+1)。

记 l=2^{p}。

我们对于每一个位置 i 维护一个二元组 (rk(p)_i,rk(p)_{i+l})，并将这些二元组以第一维为第一关键字 ，第二维为第二关键字进行排序，就可以得到 rk(p+1)_i 了。若 i>|s|，则对于 p\in[0,\lfloor\log_2|s|\rfloor+1]，rk(p)_i=0。这一步是为了令空字符（串）的字典序极小。

简单理解一下，因为字典序是从左往右比较的，如果左边的半段不一样就比较左边半段，否则比较右边半段。严谨证明的话考虑第一个不同的位置位于哪一半，结合字典序大小关系的定义容易得出上面这个结论是对的。

那么我们需要进行 \mathcal{O}(\log |s|) 层排序，若每层排序时间复杂度为 \mathcal{O}(T(|s|))，则总时间复杂度为 \mathcal{O}(T(|s|)\log |s|)。

如果使用 sort / stable_sort，可以做到 \mathcal{O}\left(|s|\log^2|s|\right)。如果使用基数排序，可以做到 \mathcal{O}(|s|\log |s|)。

AC 记录

代码

但是你会发现上面这份常数太大了。我们可以转变思路，直接求 \text{sa} 数组。具体见模板题第一篇题解代码注释，讲得很清楚。本质上是将基数排序后的下标序列作为本轮的 \text{sa} 数组，再根据定义同时求出本轮的 \text{rk} 数组。

\text{height} 数组

定义：\text{height}_i=|\text{LCP}(suf_{sa_{i-1}},suf_{sa_i})|，即排名相邻的两个后缀的最长公共前缀。

特别规定当 i=1 时 \text{height}_i=0。

代码中有时候 \text{height} 数组会以后缀的位置为下标而非后缀的排名，读者需要自行甄别。

本文代码中，常用 \text{ht} 作为 \text{height} 的简写。

可以说 \text{height} 数组是 SA 中最为精华的部分了，正是它使得 SA 能够灵活解决很多字符串问题。

使用哈希，我们容易 \mathcal{O}(|s|\log|s|) 地求出这个东西。考虑使用一些确定性的算法。

\bf{Lemma\space 1}

若 \text{suf}_{\text{sa}_i} 和 \text{suf}_{\text{sa}_j}（其中 i<j）两个后缀存在长度为 L 的公共前缀，则 \forall\,k\in[i,j)，\text{suf}_{\text{sa}_k} 与 \text{suf}_{\text{sa}_j} 存在长度为 L 的公共前缀。

\bf{Proof\space 1}

根据这个引理我们可以推出一条关键性质：

其中 i\ge 2。

$\bf{Proof}

首先容易证明它们存在这么多长度的 \text{LCP}，严谨证明的话考虑归纳法和 \min 的性质以及等号的传递性。

然后我们可以结合 \bf{Lemma\space 1} 通过反证法证明它们不存在更长的 \text{LCP}。

结合 \bf{LCP\space theory}，根据 \min 的单调性，我们可以得到：

与某个后缀 \text{suf}_i 的 \text{LCP} 长度大于等于某个定值 k 的后缀的 \text{rk} 构成一个连续的区间。

换句话说，若排名最小的与 \text{suf}_i 的 \text{LCP} 长度 \ge k 的排名为 L，最大的排名为 R，则排名在 [L,R] 内的后缀都满足其与 \text{suf}_i 的 \text{LCP} 长度大于等于该定值 k。

在求解这样的区间时，我们可以建立 \text{height} 数组的 ST 表，然后二分出两个端点。

到此为止 SA 的所有组成部分就讲解完毕了，附上一份完整的 SA 板子。

//M 为最大数据范围。
template<class T> struct STmin {
    T b[22][M];
    void build(T *a, int n) { // 对长度为 n 的数组 a 建立 min ST 表。
        for (int i = 1; i <= n; ++i) b[0][i] = a[i];
        for (int i = 1; (1 << i) <= n; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                b[i][j] = min(b[i - 1][j], b[i - 1][j + (1 << i - 1)]);
    }
    T qry(int l, int r) {
        int k = __lg(r - l + 1); return min(b[k][l], b[k][r - (1 << k) + 1]);
    }
};
struct SA {
    int n, sa[M], rk[M], y[M], cnt[M], h[M]; STmin<int> rmq;
    void build(int *a, int m) { // 对长度为 m 的字符串 a 建立 SA，默认字符集与串长同阶。
        n = m;
        for (int i = 1; i <= n; ++i) ++cnt[a[i]];
        for (int i = 1; i < M; ++i) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; --i) sa[cnt[a[i]]--] = i;
        for (int i = 2, t = rk[sa[1]] = 1; i <= n; ++i)
            rk[sa[i]] = (a[sa[i]] == a[sa[i - 1]] ? t : ++t);
        for (int w = 1, t; w <= n; w <<= 1) {
            t = 0; for (int i = n - w + 1; i <= n; ++i) y[++t] = i;
            for (int i = 1; i <= n; ++i) if (sa[i] > w) y[++t] = sa[i] - w;
            memset(cnt, 0, sizeof cnt); for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
            for (int i = 1; i <= n; ++i) cnt[i] += cnt[i - 1];
            for (int i = n; i >= 1; --i) sa[cnt[rk[y[i]]]--] = y[i];
            swap(rk, y); t = rk[sa[1]] = 1;
            for (int i = 2; i <= n; ++i)
                rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] &&
                             y[sa[i] + w] == y[sa[i - 1] + w] ? t : ++t);
            if (t == n) break;
        }
        for (int i = 1, k = 0; i <= n; ++i) {
            if (rk[i] == 1) { k = 0; continue; } if (k) --k;
            while (a[i + k] == a[sa[rk[i] - 1] + k]) ++k; h[rk[i]] = k;
        }
        rmq.build(h, n);
    }
    int lcp(int x, int y) {
        if (x == y) return n - sa[x] + 1;
        if (x > y) swap(x, y); ++x; return rmq.qry(x, y);
    }
    pair<int, int> range(int x, int y) {
        int l = 1, r = x, m, f, g;
        while (l <= r) {
            m = l + r >> 1;
            if (lcp(m, x) >= y) f = m, r = m - 1; else l = m + 1;
        }
        l = x; r = n;
        while (l <= r) {
            m = l + r >> 1;
            if (lcp(m, x) >= y) g = m, l = m + 1; else r = m - 1;
        }
        return make_pair(f, g);
    }
} S;

简单应用

本质不同子串个数

P2408 不同子串个数

• 给出长度为 n 的字符串 s，求 s 有多少个本质不同的子串。

首先，任意一个子串一定是一个后缀的前缀。比如说 s[l,r] 这个子串，它就是 s 以 l 开头的后缀长度为 r-l+1 的前缀。

那么，对于任意一种本质不同的子串，考虑所有存在它为前缀出现的后缀，在这样的排名最小的后缀中统计它。

那么就是要对于排名为 i 的后缀，计算它有多少个前缀没有在排名更小的后缀中出现过。这样的前缀个数是 n-\text{sa}_i+1-\text{height}_i 个。考虑这个后缀一共有 n-\text{sa}_i+1 个前缀，其中长度为 1 至 \text{height}_i 的前缀在排名为 i-1 的后缀中出现过，对于剩下的后缀，根据上一节中的 \bf {Lemma\space 1}，可以证明它们是第一次出现。

那么累加每一个后缀的贡献即可。

时间复杂度为 \mathcal{O}(n\log n)（不过代码里使用的是 \mathcal{O}\left(n\log^2 n\right) 的 SA），空间复杂度为 \mathcal{O}(n)。

AC Link

Code

处理多串问题

ABC362G Count Substring Query

• 给出字符串 s 和 n 个字符串 (t_1\dots,t_n)，求 t_i 在 s 中出现了多少次。

对于 t_i 的答案，考虑其在 s 的后缀中作为前缀出现，就是求 s 有多少个后缀满足它和 t_i 的 \text{LCP} 长度 \ge |t_i|。

但是我们无法直接求解来自于两个串的后缀 \text{LCP} 长度问题，于是考虑将它们中间用分隔符顺次拼接成一个大串 S。其中 |S|=|s|+n+\sum\limits_{i=1}^n|t_i|。

对于某个串以 i 为开头的后缀，我们称其在大串中的对应后缀为大串中以 i 对应位置开头的后缀。

我们需要保证两点：

• 任意两个后缀在大串中的对应后缀的大小关系和原串一致。

• 任意两个后缀在大串中的对应后缀的 \text{LCP} 长度和原串相同。

这里直接给出拼接的方法：

我们用数去表示字母，这样适用于更大的字符集。对于第 i 和第 i+1 个串之间的拼接，我们使用 i 这个数。然后每个字母在新字符集中对应的字符就是它在字典序中的编号加上最大的分隔字符。

首先来看第一点。若两个后缀 i,j 之间不存在一个是另一个的前缀，那么考虑它们的失配位置，在大串中它们的对应后缀显然也存在这个失配位置因此大小关系不变。否则，作为前缀的那个串原本失配位置上的字符由空字符变为分隔符。显然分隔符的字典序还是小于字母的。因此第一点成立。

然后看第二点，若两个后缀不存在前缀包含的关系，同样考虑失配位置在大串中仍然存在，且在其之前的字符都能作为 \text{LCP}；否则，在分隔符那一位强制失配。因此第二点也是成立的。

那么对于原问题，我们可以求，有多少个 s 的对应后缀与 t_i 的 \text{LCP} 长度 \ge|t_i|。根据前文的内容，满足后者的后缀排名形如一个区间。那么此时需要满足，s 的对应后缀的排名在这个区间内。求出这个区间后，我们可以计算区间内由多少个后缀来自于 s。这个是容易前缀和维护的。

时间复杂度为 \mathcal{O}(|S|\log |S|)，空间复杂度为 \mathcal{O}(|S|)。

AC Link & Code

习题

SP10419 POLISH - Polish Language

• 给出字符串 s，求有多少个序列 a 满足：

  • \forall i\in[1,|a|],1\le a_i\le |s|
  • \forall i\in(1,|a|],suf_{a_i}>suf_{a_{i-1}}
  • \forall i\in (1,|a|],|suf_{a_i}|>|suf_{a_{i-1}}|

  数量对 10^9+7 取模。其中字符串的比较均基于字典序大小。

• 多组数据，|s|\le 10^5。

看到后缀之间的字典序比较，先想到后缀数组。处理完之后，考虑一个一个解决限制条件。

典型二维偏序，考虑 dp。设 f_i 表示 a_{|a|}=i 的符合条件的序列数量，显然有 f_i=\sum\limits_{i<j\le n\,\land\, rk_i>rk_j}f_j+1。简单来说就是考虑第 i 位接上怎样的序列，+1 表示单独成为一个序列。

倒序枚举维护 i<j，用树状数组维护 rk_i>rk_j 即可。

设数据组数为 T，时间复杂度为 \mathcal{O}(T|s|\log |s|)，空间复杂度为 \mathcal{O}(|s|)。

提交记录 代码

P5353 树上后缀排序

• 给出一棵 n 个节点，以 1 为根的树，点 i 上有字符 c_i。定义点 i 的字符串 s_i 为从点 i 走到点 1 路径上所有点上的字符拼接而成的字符串。

• 形式化的，若点 i 到点 1 的路径为 p_1,p_2,\dots ,p_k\,(p_1=i,p_k=1)，则 s_i=\overline{c_{p_1}\dots c_{p_k}}。

• 你要对 1\sim n 这些点按照 s_i 的字典序进行排序，若字典序相同，则父亲排名小的点排名小。若仍相同，编号小的点排名小。

看到对字符串排序想到后缀排序。我们可以类比后缀排序，利用倍增的思想，每次将两条长度为 2^i 的连续的、向上的链拼起来成为长度为 2^{i+1} 的链。所以要处理树上的倍增数组，记 fa_{i,u} 为点 u 向上走 2^i 条边到达的祖先。这部分的代码：

for (int l = 0, id; (1 << l) <= n; ++l) {
    for (int i = 1; i <= n; ++i) 
        p[i] = {{rk[i], fa[l][i] ? rk[fa[l][i]] : 0}, i}; // 先比前半段，前半段相同再比后半段。
    memset(cnt, 0, sizeof cnt); 
    for (int i = 1; i <= n; ++i) ++cnt[p[i].fi.se];
    for (int i = 1; i <= n; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) tmp[cnt[p[i].fi.se]--] = p[i];
    for (int i = 1; i <= n; ++i) p[i] = tmp[i];
    memset(cnt, 0, sizeof cnt); 
    for (int i = 1; i <= n; ++i) ++cnt[p[i].fi.fi];
    for (int i = 1; i <= n; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) tmp[cnt[p[i].fi.fi]--] = p[i];
    for (int i = 1; i <= n; ++i) p[i] = tmp[i]; id = 0;
    for (int i = 1; i <= n; ++i)
        { if (i == 1 || p[i].fi != p[i - 1].fi) ++id; rk[p[i].se] = id; }
    if (id == n) { op = 1; break; }
}

关键是如何去重。这个代码求出来的 rk_i 表示将所有字符串去重后，s_i 的排名（排名定义为比它小的数的个数 +1）。我们先通过以下代码求得不去重的排名：

memset(cnt, 0, sizeof cnt); for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
for (int i = 1; i <= n; ++i) cnt[i] += cnt[i - 1];
for (int i = 1; i <= n; ++i) rk[i] = cnt[rk[i] - 1] + 1;

然后考虑两个字典序相同的字符串，它们的深度一定相同。因此用 vector 存放深度为 d 的点编号，然后从小往大处理，因为深度父亲的深度大于儿子。先将同一深度内的点按照 rk 排序。然后从头开始扫，扫出一段 \boldsymbol{rk} 相同的区间，然后再对这个区间内的点以父亲排名作为第一关键字、编号作为第二关键字排序。那么这些点的排名就是递增的，且第一个点的排名就是自己的 \boldsymbol {rk}。代码如下:

bool cmp1(int u, int v) { return rk[u] < rk[v]; }
bool cmp2(int u, int v) {
    return rk[fa[0][u]] != rk[fa[0][v]] ? rk[fa[0][u]] < rk[fa[0][v]] : u < v;
}
for (int i = 0; i < n; ++i) {
    sort(h[i].begin(), h[i].end(), cmp1);
    for (int j = 0, k, l = h[i].size(), id; j < l; j = k) {
        for (k = j; k < l && rk[h[i][k]] == rk[h[i][j]]; ++k);
        sort(h[i].begin() + j, h[i].begin() + k, cmp2); id = rk[h[i][j]] - 1;
        for (int d = j; d < k; ++d) rk[h[i][d]] = ++id;
    }
}

去完重之后，如果用后缀排序中的名称来说，别忘记你输出的是 \boldsymbol{sa} 数组而不是 \boldsymbol{rk} 数组，你要再做一遍 sa_{rk_i}=i。

现在来算时间复杂度，倍增处理 fa 数组以及倍增求 rk 都是 \mathcal{O}(n\log n) 的，至于去重，其实就是把“将长度为 n 的数组分成若干段，对每段分别进行排序并从左到右扫描”这个操作做了两次，根据乘法分配律和加法结合律，可以算出这部分的时间复杂度为 \mathcal{O}(n\log n)。

综上，本做法时间、空间复杂度均为 \mathcal{O}(n\log n)。

评测记录 代码

AT_s8pc_2_e 部分文字列

• 给出一个字符串 S，求 S 的所有本质不同子串的长度之和。

看到本质不同子串，先做后缀排序把 \text{height} 数组求出来，然后排名为 i 的后缀能带来的本质不同子串个数为 |S|-sa_i+1-\text{height}_i，这些子串的长度为 \text{height}_i+1\sim |S|-sa_i+1，等差数列求和计算即可。

时间复杂度为 \mathcal{O}(|S|\log |S|)，空间复杂度为 \mathcal{O}(|S|)。由于是 AT 远古题，所以行末要输出换行。

提交记录（含代码）

CF149E Martian Strings

• 给出字符串 s，以及 m 个询问串 p_i，每次询问是否能找到两个不交的区间 [a,b],[c,d] 使得 \overline{s_as_{a+1}\dots s_bs_cs_{c+1}\dots s_d} = p_i。

考虑将所有串拼成一个大串 S，做一遍后缀排序，求出 sa,rk,\text{height} 数组。

对于每一组询问，考虑枚举 j 表示找到 [a,b],[c,d] 使得 \overline{s_as_{a+1}\dots s_b}=\overline{p_{i_1}p_{i_2}\dots p_{i_{j}}},\overline{s_bs_{c+1}\dots s_d}=\overline{p_{i_{j+1}}p_{i_{j+2}}\dots p_{i_{|p_i|}}}。可以通过二分 + ST 表求出满足条件的后缀的排名区间。

我们考虑选择最左边的 [a,b] 以及最右边的 [c,d]，这样一定不劣。因此考虑以排名为下标建立 ST 表维护某个排名区间内，\boldsymbol{\le n} 的最左、左右后缀的位置。然后判断这两个位置截取出来的子串是否相交即可。

时间、空间复杂度均为 \mathcal{O}(|S|\log |S|)。

提交记录（含代码）

CF316G3 Good Substrings

附 CF316G1 Good Substrings，CF316G2 Good Substrings。

• 给出字符串 s，以及 n 个限制，每个限制形如 t_i,l_i,r_i，一个字符串满足该条限制，当且仅当它在字符串 t_i 中的出现次数在 [l_i,r_i] 之间。

• 求 s 有多少个本质不同的子串满足所有限制。

记 s[l,r] 为字符串 s 以 s_l 开头，以 s_r 结尾的子串，形式化的，s[l,r]=\overline{s_l\dots s_r}。

看到「本质不同子串」，想到后缀数组。先将所有字符串用奇怪字符拼起来（记大串为 S）做后缀排序求出 sa,rk,\text{height} 数组并对 \text{height} 数组维护 ST 表。

对于一个字符串 s，我们知道排名为 i 的后缀带来的本质不同子串是 s[sa_i,\text{height}_i+1]\sim s[sa_i,|s|] 这些，然后你会发现这些子串的出现次数随着长度递增不升。

因为若有一个长串出现若干次，我的短串也被这个长串包含，至少出现了这么多次。

考虑二分出最短的满足所有限制上界的字符串长度 ans_l 以及最长的满足所有限制下界的字符串长度 ans_r，那么这个后缀就可以带来 ans_r-ans_l+1 个满足所有限制的本质不同子串。

维护一个前缀和数组 sum_{j,i}，表示排名为 1\sim i 的后缀中，有多少个后缀是 t_j 带来的。我们又知道对于一个子串，出现它的后缀的排名是一段连续的区间。套路用二分和 ST 表求 \text{LCP} 得到这个区间 [L,R]。问题变成了判断区间内某个数 i 出现次数是否（不）超过给定的值。用 sum_{i,R}-sum_{i,L-1} 表示出其出现次数，由于 n 很小，枚举判断即可。这样这题基本就做完了。

还有一个地方需要注意，我们要求的是原串 \boldsymbol{s} 某个后缀带来的本质不同子串个数，但是现在把所有字符接在一起，\text{height} 数组并是大串 S 中两个排名相邻的后缀的 \text{LCP}。所以我们要按排名枚举 S 的后缀，如果它是 s 的后缀就统计答案。然后你对 S 后缀排序，原串 \boldsymbol{s} 中的所有后缀也是有序的，不然它们在 S 中也是无序的，相当于你就没排序。 因此直接记录上一个为原串中的某个后缀的排名 la，那么我要的 \text{height}，原串 s 中排名相邻两个后缀的 \text{LCP}，就是 S 中 S[la,|S|] 和当前后缀的 \text{LCP}。后面接的东西不影响，因为你接了奇怪字符，在那一位一定失配，不会影响 \text{LCP} 长度。

时间复杂度为 \mathcal{O}(|S|\log |s| (n+\log|S|))，空间复杂度为 \mathcal{O}(|S|\log |S|+n|S|)。

提交记录（含代码）

UVA1502 GRE Words

双倍经验

• 给出 n 个字符串 s_1\sim s_n，第 i 个字符串有权值 w_i。选出一个子序列 a_1\sim a_k，满足 \forall\,i\in[1,k),a_i<a_{i+1} 且 s_{a_i} 是 s_{a_{i+1}} 的子串。求 \sum\limits_{i=1}^kw_{a_i} 的最大值。可以为空，此时权值为 \boldsymbol 0。

记 N=\sum\limits_{i=1}^n|s_i|。

考虑 dp。设 f_i 表示以 i 开头的最长子序列，则 f_i=\max\limits_{j\in(i,n]\land \,s_i\text{ is a substring of }s_j} f_j+w_i。

将所有串拼成一个大串 S 进行后缀排序。则 j 满足条件，当且仅当 s_j 中有一个后缀与 s_i 的最长公共前缀长度不少于 |s_j|。

这样的后缀排名形如一个区间 [L,R]。考虑线段树维护。区间 [l,r] 的信息为：当前包含排名为 [l,r] 中的后缀的字符串中，f_j 的最大值。

那么转移就是区间最大值。可能会重复贡献一些 f_j，但由于是取 \max 所以没关系。

转移完后在线段树上对 s_i 的所有后缀排名对应的位置进行单点修改。

时空复杂度均为 \mathcal{O}(N\log N)。可以把 \text{height} 数组用线段树维护然后线段树上二分得到排名区间，这样空间是线性。

AC Link / AC Code

SP8093 JZPGYZ - Sevenk Love Oimaster

• 给出 n 个模板串 s_1\sim s_n 和 m 个查询串 t_1\sim t_m，每次询问一个查询串是多少个模板串的子串。

先将所有字符串用奇怪字符拼成一个大串 S 然后做一遍后缀排序，求出 sa,rk,\text{height} 等数组。

对于每一个询问串，以它为前缀的后缀的排名一定是一个区间，考虑二分出这个区间 [L,R]。

我们记排名为 i 的后缀的颜色 col_i 为它是哪个模板串的后缀。则要求区间 [L,R] 内有多少种不同的颜色。

主席树维护每一个位置的前驱，数有多少个前驱在区间外即可。但是询问串之间也可能存在包含关系，所以要数的颜色必须是 [1,n] 内的颜色。

因此主席树的一个节点的定义为：当前版本中，有多少个位置满足这个位置的颜色在 [1,n] 内，且该位置的前驱在该区间内。插入的时候，若当前位置的颜色在 [1,n] 内则插入，否则继承上一个版本。

时间、空间复杂度均为 \mathcal{O}(|S|\log |S|)。

提交记录 代码

CF232D Fence

• 给出序列 a_1\sim a_n，有 q 次询问，每次询问给出 [l,r]，求有多少个区间 [x,y] 满足 y-x=r-l，[x,y] \bigcap \,[l,r]=\varnothing 且 \forall \,i\in[0,r-l],a_{l+i}+a_{x+i}=a_{l}+a_x。

tags：

• \text{binary search}
• \text{data structures}
• \text{string suffix structures}
• \color{red}*2900

原题就是让我们求出有多少个满足条件的左端点。

我们记原数组的差分数组 d_i=a_i-a_{i-1}\,(i\in(1,n])。认为 \boldsymbol{d_1} 没有意义，即不存在，其值不与任何一个 \boldsymbol{d_i} 相同。则满足第二个条件的充要条件是 \forall \,i\in(0,r-l],d_{l+i}=-d_{x+i}。

• 证明：

根据已知条件可以推出：

• a_{l+i}+a_{x+i}=a_l+a_x\Leftrightarrow a_{l+i}-a_l=a_x-a_{x+i}
• a_{l+i-1}+a_{x+i-1}=a_l+a_x\Leftrightarrow a_{l+i-1}-a_l=a_{x}-a_{x+i-1}

两式相减即可得到 a_{l+i}-a_{l+i-1}=a_{x+i-1}-a_{x+i}，即 d_{l+i}=-d_{x+i}。

我们若倍长 d，且令 d_i=-d_{i-n}\,(i\in(n,2n])，则上述条件等价于 d_{l+i}=d_{x+n+i}。我们要统计有多少个 x，就可以去统计有多少个 x+n，同理可以去统计有多少个 \boldsymbol{x+n+1}。

为什么要做这一步转化呢？我们发现，对于 d[l+1,2n] 和 d[x+n+1,2n] 这两个后缀，它们存在 \boldsymbol{d[l+1,r]} 和 \boldsymbol{d[x+n+1,x+n+r-l]} 这一段长度为 \boldsymbol{r-l} 的公共前缀。考虑对差分数组进行后缀排序，则可以二分 + ST 表求出与后缀 d[l+1,2n] 的 \text{LCP} 长度不小于 r-l 的排名区间。然后根据不交、长度相等的限制以及差分数组的定义，可以得到 x+n+1 的范围是 [n+2,n+2l-r]\bigcup\, [n+r+2,2n+l-r+1]。

这就是个二维数点，在线主席树或离线扫描线 + 树状数组维护一下就行了。

• 注意

使用上述统计方法的前提是存在差分数组。当 l=r 时，区间内不存在差分数组，不能这样统计。

不过容易得知此时答案即为 n-1，特判一下即可。

代码里用的是主席树，时间、空间复杂度均为 \mathcal{O}(n\log n)。

提交记录（\color{limegreen} \bf{Accepted} \bf{483\,\text{ms}\,/\,73952\,\text{KB}}，含代码）

UVA1673 数字子串的和 str2int

• 给出 n 个由阿拉伯数字构成的字符串 (s_1,\dots,s_n)，对于一个子串 s_i[l,r]，称其权值为 去除前导零 后得到的十进制数的数值。求 (s_1,\dots,s_n) 中所有 本质不同 的权值和，模 2012 的值。

记字符串 t 的权值为 v(t)。

将所有字符串用分隔符拼成大串 S 并进行后缀排序。此时 |S|=n+\sum\limits_{i=1}^n|s_i|。

要求的答案可以转化为 S 所有 不跨过分隔符 且 不含前导零 的 本质不同子串 的权值和。

因为所有这样的本质不同子串都对应了唯一一种权值，而且对于原来的任意一种权值，一定存在一个 不含前导零 的子串权值为她。考虑一个含前导零的子串提供的权值，将前导零去掉后仍是原串的子串，且权值不变。

对于每个原串，倒序枚举后缀，若其不含前导零则计算她带来的本质不同子串的权值和。记 s_i 在 S 中的位置为 [L_i,R_i]。

考虑以 i 为起点的后缀，若她位于 s_j 这个串，则她带来的本质不同子串为一段右端点连续的子串 \left(S\left[i,i+\text{height}_{\text{rk}_i}\right],\dots,S[i,R_j]\right)。

考虑如何快速计算这些串的权值。我们发现 S\left[i,i+\text{height}_{\text{rk}_i}-1\right] 均被计算，且最低位的权值分别为 10,10^2,\dots,10^{R_j-i-\text{height}_{\text{rk}_i}+1}。多项式哈希维护子串权值，并维护 10 的幂的前缀和即可。

剩下的部分是 \left(S\left[i+\text{height}_{\text{rk}_i}+1,i+\text{height}_{\text{rk}_i}+1\right],\dots,S\left[i+\text{height}_{\text{rk}_i}+1,R_j\right]\right) 这些子串的权值和。

考虑后缀和维护。对于当前枚举的原串 s_j，维护 k_i=\sum\limits_{u=i}^{R_j}v(S[i,u])。当 i 左移一位时，会新加入 S_i 这个字符，对于以 i 开头的每个串，S_i 分别位于权值为 1,10,10^2,\dots,10^{R_j-i} 这些位置上。同样维护 10 的幂前缀和计算即可。

时间复杂度为 \mathcal{O}(|S|\log |S|)，空间复杂度为 \mathcal{O}(|S|)。

Code

P4143 采集矿石

• 给出字符串 s，以及数组 a_1\sim a_{|s|}。

• 定义一个子串的排名为：字典序比它大的本质不同的子串个数 +1。

• 定义一个子串 s[l,r] 的权值为 \sum\limits_{i=l}^ra_i。

• 求有多少个子串的排名等于权值。

首先对 s 进行后缀排序，然后考虑每一个左端点 l，不难发现随着右端点 r 的增大，子串的排名单调递减，权值单调不降。

所以可以二分出满足条件的最小 / 大右端点。

考虑如何求出一个子串 t 的排名。可以用本质不同子串数减去比它小的。

前半部分运用经典结论即为 \sum\limits_{i=1}^n (|s|-sa_i+1-\text{height}_i)，我们考虑如何求比它小的本质不同子串数。

可以二分出以这个子串为前缀的后缀排名区间 [L,R]。答案即为排名为 \boldsymbol{[1,L)} 的后缀带来的本质不同子串个数加上排名为 L 的后带来的本质不同字串中她的前缀。

后面那条是显然的，下证前面的条件。

• 充分性：

  若一个子串 str 在排名为 [1,L) 的后缀中作为前缀出现，那么这个后缀 s[i,|s|] 与 s[l,|s|] 的 \text{LCP} 长度一定小于 \boldsymbol{|t|}。即两个后缀可以在第 |t| 个位置之前可以找到不相同的位置。而由于 s[i,|s|] 这个后缀排名更小，在这个位置一定 s[i,|s|] 这个后缀小于 s[l,|s|]。

  考虑 str 是否跨过这个位置，若不是，则在前 |str| 位两串相同，第 |str|+1 位 str 为空，字典序极小。

  若跨过，则 str 在这个位置小于 t。

• 必要性：

  考虑这两个子串第一次不同是在某个位置，这个位置一定在两个后缀中。

正确性证好了。这个东西也是考虑每个后缀带来的本质不同子串。即可以这么求：

于是做完了。时间复杂度为 \mathcal{O}(|s|\log^2|s|)，空间复杂度为 \mathcal{O}(|s|)。

提交记录 代码

ABC280Ex Substring Sort

• 给出 n 个字符串 s_1\sim s_n。记 F(i,l,r) 表示 s_i[l,r] 这个子串。将所有存在的 F(i,l,r) 非降排序。q 次询问，求出排在第 k 位的 F(i,l,r)。如有多解输出任意一个。

先将所有字符串拼成大串 S。其中 \mathcal{O}(|S|)=\mathcal{O}\left(n+\sum\limits_{i=1}^n|s_i|\right)。对 S 进行后缀排序。

称一个串在排名为 i 的后缀中第一次作为前缀出现，当且仅当：不存在 j<i，使得这个串在排名为 j 的后缀中作为前缀出现。

对于 S 中排名为 i 的后缀，预处理 sum_i 表示有多少种本质不同的原串中的子串在这个后缀中第一次作为前缀出现；预处理 tot_i 表示有多少个原串中的子串在这个后缀中作为前缀出现。然后分别对这两个数组求前缀和，记为 ssum_i 和 stot_i（代码中用的是同一个数组）。

考虑求出答案是第几大的本质不同子串。容易发现排在第 k 位等价于，它是最大的一种子串，使得小于它的子串数量小于 k。这个有单调性，可以二分利用 ssum_i 判断求。

记二分的子串为 str。考虑对于每个后缀统计小于 str 的子串数量。先找到它第一次出现在哪个排名的后缀中，设这个排名为 p。分为 [1,p) 和 [p,|S|] 两部分。

对于第一部分，这些后缀的所有前缀都小于 str。因为若某个前缀 pre 是 str 前缀，其必然是真前缀。不然 p 就不是 str 第一次出现的位置。那么 pre 字典序小于 str。否则，它们跨过了 \text{LCP}，又因为 [1,p) 的后缀排名更小，所以 pre 在 \text{LCP} 后的那个位置上一定小于 str，因此 pre 字典序小于 str。

对于第二部分，答案为 \sum\limits_{i=p}^{|S|}\min\{|\text{LCP}(S[i,|S|],S[p,|S|])|,|str|-1\}。同样考虑为 pre 为 str 真前缀以及跨过 \text{LCP} 的情况。

第一部分答案即为 stot_{p-1}。第二部分考虑将 \min 拆开。由于 |\text{LCP}(S[i,|S|],S[p,|S|])|=\min\limits_{j=p+1}^i \text{height}_j，这个式子的值是单调不升的。可以二分出一个分界点 pos 使得当 i\in[p,pos] 时 \min\{|\text{LCP}(S[i,|S|],S[p,|S|])|,|str|-1\}=|str|-1；当 i\in(pos,|S|) 时 \min\{|\text{LCP}(S[i,|S|],S[p,|S|])|,|str|-1\}=\min\limits_{j=p+1}^i \text{height}_j。显然有 pos\ge p，因为 p 这个后缀以 str 为前缀。

那么第一种情况的贡献就是 (pos-p+1)(|str|-1)；至于后一种情况，根据 \min 的结合律，可以将其改写成 \sum\limits_{i=pos+1}^{|S|}\min\limits_{j=pos+1}^{i}\text{height}_j。记为 f_x=\sum\limits_{i=x}^{|S|}\min\limits_{j=x}^{i}\text{height}_j。由于没有修改，考虑预处理。

可以用单调栈，对于每个 x 求出最小的 y，满足 y>x 且 \text{height}_y<\text{height}_x。记这个 y 为 nxt_x。同样将 f_x 分为 i\in[x,nxt_x) 和 i\in[nxt_x,|S|] 两部分。对于第一部分，根据 nxt_x 的定义可知这些 [x,i] 的最小值均为 \text{height}_x，贡献为 (nxt_x-x)\text{height}_x；对于第二部分，再运用 \min 的结合律写成 \sum\limits_{i=nxt_x}^{|S|}\min\limits_{j=nxt_x}^i \text{height}_i，你会发现它就是 f_{nxt_x}。于是我们得到了 f_x 的求法：

此时 s[i,r]<s[k,r]，当且仅当 \boldsymbol{i<k} 且 \bf{|LCP}\boldsymbol{(s[i,n],s[k,n])|\le r-k}，或 \boldsymbol{i>k}。

• 充分性

  当 i<k 且 |\text{LCP}(s[i,n],s[k,n])|\le r-k 时，两个后缀第一个不同的位置一定均在 s[i,r] 和 s[k,r] 中出现，此时比较两个串也是比较这两位，因为 rk_i<rk_k，故 s[i,r]<s[k,r]。

  当 i>k 时，若两个后缀第一个不同的位置均在 [l,r] 中出现则与上一种情况合理，否则 s[i,r] 是 s[k,r] 的前缀，故 s[i,r]<s[k,r]。

• 必要性

  考虑 s[i,r]<s[k,r] 时，若 i<k，则一定有 |\text{LCP}(s[i,n],s[k,n])|\le r-k，否则 s[k,r] 为 s[i,r] 前缀，此时 s[k,r]<s[i,r]。若 i>k，则已经满足条件。

• 做法

  分 i<k 和 i>k 讨论。

  若 i<k，则需要统计有多少个后缀 s[i,n] 满足 i\in[l,k)，rk_i<rk_k 且 \text{|LCP}(s[i,n],s[k,n])|\le r-k。降第三个限制转化为 \text{height} 数组的限制，其等价于 \min\limits_{j=rk_i+1}^{rk_k}\text{height}_j\le r-k。容易发现此时满足条件的 i 的 rk_i 在一个前缀 [1,x] 中，其中 x<rk_k。二分 + RMQ 求出这个 x，问题转化成统计有多少个点对满足 i\in[l,k) 且 rk_i\in[1,x]，主席树维护即可。

  若 i>k，则需要统计有多少个后缀 s[i,n] 满足 i\in(k,r] 且 rk_i<rk_k，同样主席树维护。

• rk_i>rk_k

  此时 s[i,r]<s[k,r]，当且仅当 \boldsymbol{i>k} 且 \bf{|LCP}\boldsymbol{(s[i,n],s[k,n])|\ge r-i+1}。

  • 充分性

    容易发现此时 s[i,r] 为 s[k,r] 前缀，故 s[i,r]<s[k,r]。

  • 必要性

    考虑证明不满足上述条件则 s[i,r]>s[k,r]。

    若 i<k，如果两个串第一个不同的位置均在 [l,r] 中出现，因为 rk_k<rk_i，所以 s[i,r]>s[k,r]。否则，s[k,r] 为 s[i,r] 前缀，此时 s[i,r]>s[k,r]。

    若 i>k 且 \text{|LCP}(s[i,n],s[k,n])|\le r-i，则两个串第一个不同的位置一定均在 [l,r] 中出现，因为 rk_k<rk_i，所以 s[i,r]>s[k,r]。

  • 做法（本题解最核心部分）

    以排名为下标做一遍序列分治，将询问挂在 rk_k 上，每层分治考虑右半边对左半边的贡献（很像 cdq 分治）并左右递归下去统计，则对于任意一个合法的后缀，根据分治树的形态，一定存在且仅存在一层分治，使得询问在左半边，后缀在右半边，此时它被统计到。并且，在每层分治中我们统计合法的贡献，可以做到不重不漏。

    设分治区间为 [L,R]，中点 mid=\left\lfloor\dfrac{L+R}{2}\right\rfloor。

    对于左半边的一个询问 (l,r,k)，我们要统计右半边有多少个 i，满足：

    • sa_i\in(k,r]
    • \text{|LCP}(s[k,n],s[sa_i,n])|\ge r-sa_i+1\Leftrightarrow \min\limits_{j=rk_k+1}^i \text{height}_j\ge r-sa_i+1

    采用序列分治的一般套路，从 mid\rightarrow L 扫描询问。设当前扫到的排名为 K。维护变量 mn=\min\limits_{j=K+1}^{mid}\text{height}_j。对于右半区间维护前缀 \text{height} 最小值，即 pmn_i=\min\limits_{j=mid+1}^{i}\text{height}_j。则对于当前扫到的排名上的询问，条件中的 \min\limits_{j=rk_k+1}^i \text{height}_j\ge r-i+1 可以转化为 \min\{mn,pmn_i\}。

    容易发现 pmn_i 具有单调（不升）性。可以找到一个分界点 p，使得当 i\in[mid+1,p) 时，\min\{mn,pmn_i\}=mn；当 i\in[p,R] 时，\min\{mn,pmn_i\}=pmn_i。

    对于分界点左边的情况，就是统计有多少 i 满足：

    • sa_i\in(k,r]
    • mn \ge r-sa_i+1\Leftrightarrow sa_i\ge r-mn+1
    • i\in[mid+1,p)

    整理一下就是：

    • sa_i\in[\max\{r-mn,k\}+1,r]
    • i\in[mid+1,p)

    容易主席树维护。

    对于分界点右边的情况，就是统计有多少 i 满足：

    • sa_i\in(k,r]
    • pmn_i\ge r-sa_i+1\Leftrightarrow sa_i+pmn_i\ge r+1
    • i\in [p,R]

    你发现这是个三维数点，好像行不通啊！

    然后就是一个很妙的转化了。考虑正难则反。你发现对于分界点右边的情况，sa_i+pmn_i\ge r+1\Rightarrow sa_i+mn\ge r+1，因为在分界点右边 pmn_i=\min\{pmn_i,mn\}。所以可以先统计满足以下条件的 i 的个数：

    • sa_i\in[\max\{r-mn,k\}+1,r]
    • i\in [p,R]

    算上分界点左边的统计，相当于要统计右半边满足 sa_i\in[\max\{r-mn,k\}+1,r] 的 i 个数。可以 vector + 二分统计。考虑哪些不合法的被统计了，显然它满足：

    • sa_i\in[\max\{r-mn,k\}+1,r]
    • sa_i+pmn_i\le r
    • i\in[p,R]

    于是就要减去这样的 i 的个数。实际上这还是个三维数点，不过你发现，\boldsymbol{\nexists\,i\in[mid+1,p),sa_i\in[\max\{r-mn,k\}+1,r]\land sa_i+pmn_i\le r}。即分界点左边不存在满足前两个条件的 i。

    为什么呢？首先 sa_i\in[\max\{r-mn,k\}+1,r] 的必要条件是 sa_i\ge r-mn+1。你考虑分界点左边 mn\le pmn_i，若 sa_i\ge r-mn+1 即 sa_i+mn\ge r+1，则一定有 sa_i+pmn_i\ge r+1。反之，若 sa_i+pmn_i\le r，则一定有 sa_i+mn \le r 即 sa_i\le r-mn。因此两个条件不能被同时满足。

    所以我们直接大胆忽略 i\in[p,R] 这个条件，统计全局（当前分治区间） sa_i\in[\max\{r-mn,k\}+1,r] 且 sa_i+pmn_i\le r 的 i 的个数。同样是二维数点，主席树维护即可。

至此两类统计都解决了。接下来算复杂度。因为有主席树和 ST 表，所以空间复杂度显然为 \mathcal{O}(N\log N)。

至于时间复杂度（只说每个部分的瓶颈），后缀排序是 \mathcal{O}(N\log^2 N) 的（因为不是瓶颈所以没用基数排序优化）。rk_i<rk_k 的统计需要往主席树中插入 \mathcal{O}(N) 个点对，并且每次询问要进行一次 \mathcal{O}(1) 检查（ST 表）的二分以及 \mathcal{O}(\log N) 的主席树查询，时间复杂度为 \mathcal{O}((N+M)\log N)。

对于分治部分，每个询问会在 \mathcal{O}(\log N) 层分治中被扫到，每次扫到要做一次主席树查询和 vector 二分，单次是 \mathcal{O}(\log N)。每个点对会在 \mathcal{O}(\log N) 层分治中被插入主席树，单次也是 \mathcal{O}(\log N)。这部分的时间复杂度为 \mathcal{O}((N+M)\log^2 N)。为了维护主席树，每层分治需要将点对进行排序，由于每层分治的区间总长度为 N，因此任意一层排序的 \log 不超过 \mathcal{O}(\log N)。容易通过乘法分配律得到是 \mathcal{O}(N\log^2 N) 的。因此，分治部分的总时间复杂度为 \mathcal{O}((N+M)\log ^2 N)。

综上，本做法时间复杂度为 \mathcal{O}((N+M)\log^2 N)，空间复杂度为 \mathcal{O}(N\log N)，可以接受。

代码

AC 记录

CF1098F Ж-function

• 给出长度为 n 的字符串 s。定义 Ж(l,r)=\sum\limits_{i=l}^r|\text{lcp}(s[l,r],s[i,r])|。q 次询问，每次给出 l,r，查询 Ж(l,r)。

先后缀排序。

将子串的 \text{lcp} 搞成后缀的 \text{lcp}，则 Ж(l,r)=\sum\limits_{i=l}^r\min\{|\text{lcp}(s[l,n],s[i,n])|,r-i+1\}。

然后将询问挂在 \text{rk}_{l} 上，分别计算 \text{rk}_i<\text{rk}_l 和 \text{rk}_i>\text{rk}_l 的贡献，最后算上 l 本身的贡献。此时可以将 \text{lcp} 的限制转化成 \text{height} 数组的限制，即：

我们先以 \text{rk}_i<\text{rk}_l 的情况为例讲一下怎么算贡献。

对 \text{height} 数组进行序列分治（其实此处比较像 cdq 分治），记当前分治区间为 [L,R]，中点 M=\dfrac{L+R}{2}，N=R-L+1。考虑当前层右半边对左半边的贡献。

记 \text{pre}_j=\min\limits_{k=M+1}^R\text{height}_k。对于左半边按 M\rightarrow L 的顺序扫描 i，并同时记录 \text{mn}=\min\limits_{k=i+1}^M\text{height}_j。

考虑挂在 i 上的一个询问 (l,r)。

此时，存在 p\in[M+1,R] 使得当 j\in[M+1,p) 时 \text{mn}\le \text{pre}_j；当 j\in[p,R] 时 \text{mn}>\text{pre}_j。

化简第二层 \min\{\}，那么右半边对 (l,r) 的贡献就是：

由于 i 递减，\text{mn} 不升，因此 p 不降，最多递增 \mathcal{O}(N) 次。

然后将 \min\{\} 拆开，即讨论一下谁是最小值，此处我们只讨论前面那个数更小（不等于）的情况。因为两种讨论都是类似的。

对于 j\in[M+1,p) 的部分，我们要求 \sum\limits_{j=M+1}^{p-1}([l\le \text{sa}_j\le r\land \text{mn}<r-\text{sa}_j+1]\cdot \text{mn})，提取公因式 \text{mn} 后发现是关于 j,\text{sa}_j 的二维偏序。可以用树状数组维护 \text{sa}_j，在 p 移动时更新树状数组（就是扫描线）。

对于 j\in[p,R] 的部分，我们要求 \sum\limits_{j=p}^R([l\le \text{sa}_j\le r\land \text{pre}_j<r-\text{sa}_j+1]\cdot \text{pre}_j)。

接下来是重点，也是这个套路最巧妙的一步。

如果按照之前的方法找偏序关系，发现是关于 j,\text{sa}_j,\text{sa}_j+\text{pre}_j 的三维偏序。你要是在分治内部再套个树套树 / cdq 分治的话复杂度肯定爆炸。

我们先求 \sum\limits_{j=p}^R([l\le \text{sa}_j\le r\land \text{mn}<r-\text{sa}_j+1]\cdot \text{pre}_j)。这东西拆开后是二维偏序，树状数组类似维护。

由于右半边 \text{pre}_j<\text{mn}，漏算的贡献是 \sum\limits_{j=p}^R([l\le \text{sa}_j\le r\land \text{pre}_j<r-\text{sa}_j+1\le \text{mn}]\cdot \text{pre}_j)。你发现这还是个三维偏序，那不是白搞？别急，你发现当 j\in[M+1,p) 时，\text{mn}\le \text{pre}_j，即 \text{pre}_j<r-\text{sa}_j+1\le \text{mn} 不成立。因此直接忽略掉 j 这一维限制即可！那么剩下的就是关于 \text{sa}_j,\text{sa}_j+\text{pre}_j 的二维偏序，由于扫描的是 p，所以离线下来再树状数组维护即可。

那么这种情况就讨论完了。剩下的一种情况是类似的，尤其是对于 [p,R] 这部分贡献三维偏序转二维偏序的时候，都是将 \text{mn} 代入二维偏序，再加上 (\text{pre}_j,\text{mn}] 漏算的 / 减去 (\text{pre}_j,\text{mn}] 多算的，然后通过不同区间 \text{pre}_j,\text{mn} 大小关系忽略 j 那一维限制。

至于 \text{rk}_i>\text{rk}_l 的情况，只是需要再分治的时候换成扫描右半边，对左半边维护后缀最小值，计算贡献部分经过瞪眼观察或手推后都可以发现是一模一样的。

那么这题就做完了。

记 i 这个位置上挂了 Q_i 个询问。可以发现一层分治的时间复杂度为 \mathcal{O}\left(\left(N+\sum \limits_{i=L}^RQ_i\right)\log n\right)。考虑到分治树的深度为 \mathcal{O}(\log n)，且对于同一深度的区间而言 \sum N=n,\sum Q_i=q。所以总的时间复杂度为 \mathcal{O}\left((n+q)\log ^2 n\right)，空间复杂度为 \mathcal{O}(n+q)。常数较大，但是目前洛谷最优解第三。实现细节看代码吧。

AC Link & Code

P4482 [BJWC2018] Border 的四种求法

• 给出字符串 s，q 次询问 l,r，求 s[l,r] 的 Border 长度。

记 n=|s|。

考虑套用 CF1098F Ж-function 的做法，对于每次询问相当于求 (l,r] 中最小的 p，使得 |\text{LCP}(s[l,n],s[p,n])|\ge r-p+1。那么答案为 r-p+1。

后缀排序求出 \text{height} 数组，将 \text{LCP} 转化为区间最小值。考虑对于 \text{rk}_p<\text{rk}_l 和 \text{rk}_p>\text{rk}_l 的部分分别求解。

以后面那种为例。考虑求满足如上条件的后缀的 排名 中，\text{sa} 的最小值。相当于要求在满足 w>\text{rk}_l，\min\limits_{\text{rk}_l< i\le w}\text{height}_i\ge r-\text{sa}_w+1 且 l<\text{sa}_w\le r 的 w 中，\text{sa}_w 的最小值。

考虑离线，将询问挂在 \text{rk}_l 上，对 \text{height} 数组序列分治。记当前分治区间为 [L,R]，中点 m=\left\lfloor\dfrac{L+R}{2}\right\rfloor。考虑右半边对左半边的贡献。

对于右半边的一个位置 i，记 k_i=\min\limits_{m+1\le j\le i}\text{height}_j。对于左半边，从右往左扫描 i，维护 \text{mn}=\min\limits_{i<j\le m}\text{height}_j，同时更新挂在她上的询问的答案。则 \min\limits_{i<x\le w}\text{height}_w 可以表示成 \min\{\text{mn},k_w\}。

考虑拆 \min。对于 \text{mn}\le k_w 的部分，要求满足 \begin{cases}l<\text{sa}_w\le r\\r-\text{sa}_w+1\le \text{mn}\end{cases} 的 w 中，\text{sa}_w 的最小值。这是关于 k_w 和 \text{sa}_w 两维限制的偏序问题。

对于 \text{mn}>k_w 的部分，要求满足 \begin{cases}l<\text{sa}_w\le r\\r-\text{sa}_w+1\le k_w\end{cases} 的 w 中，\text{sa}_w 的最小值。这是关于 k_w,\text{sa}_w,\text{sa}_w+k_w 三维限制的偏序问题。

小 L 发现这题不像 CF1098F Ж-function ，求的是个数可以差分和容斥。如果直接做要 \log 满天飞了！虽然 3\log 貌似也能过，但是小 L 是可爱的女孩子，她不喜欢这样丑陋的做法。

考虑改变思路，能否转化成求个数的问题然后套用 CF1098F Ж-function 的做法？考虑求 l<\text{sa}_w\le x 的范围内满足条件的排名个数，则最小的 \text{sa}_w 就是最小的使得满足条件排名个数不为 0 的 x。

考虑如何求个数。对于 \text{mn}\le k_w 的部分，要求满足 \begin{cases}l<\text{sa}_w\le x\\r-\text{sa}_w+1\le \text{mn}\end{cases} 的 w 个数；对于 \text{mn}>k_w 的部分，要求满足 \begin{cases}l<\text{sa}_w\le k\\r-\text{sa}_w+1\le k_w\end{cases} 的 w 个数。后者是三维数点，考虑继续简化。

考虑容斥，用满足 \begin{cases}\text{mn}>k_w\\l<\text{sa}_w\le k\\r-\text{sa}_w+1\le \text{mn}\end{cases} 的 w 个数减去 \begin{cases}\text{mn}>k_w\\l<\text{sa}_w\le k\\k_w< r-\text{sa}_w+1\le\text{mn}\end{cases} 的 w 个数。前者可以和 \text{mn}\le k_w 的部分合并转化成全局 r-\text{sa}_w+1\le \text{mn} 个数；对于后者，我们发现满足第三个条件一定满足第一个条件，因此进一步转化为求 \begin{cases}l<\text{sa}_w\le k\\k_w< r-\text{sa}_w+1\le\text{mn}\end{cases} 的个数，这样她就是关于 \text{sa}_w 和 \text{sa}_w+k_w 两维的二维数点了！

将转化后的限制整理一下，即加上 \max\{r-\text{mn},l\}+1\le \text{sa}_w\le r 的 w 个数再减去 \begin{cases}\max\{r-\text{mn},l\}+1\le w\le r\\\text{sa}_w+k_w\le r\end{cases} 的 w 个数。

到这里，由于满足条件的 w 个数是随 x 增加非降的，朴素的想法是考虑二分 x，然后按照上述方式数点。但是仍是 3\log，还是不优雅。但是小 L 发现要求的 \text{sa}_w 还出现在限制中，并且加上、减去的部分对于 \text{sa}_w 的限制还是相同的。可以考虑利用这一点性质。

发现二分和数据结构契合的不是很好，考虑 直接在数据结构上二分。维护两棵线段树 t_1,t_2。t_1 是全局 \text{sa}_w 的权值线段树，t_2 是满足 \text{sa}_w+k_w\le r 的 w 的 \text{sa}_w 的权值线段树，均维护每个权值的出现次数。

在字符串总长度为 n 的长为 m 的字符串序列 s_1\sim s_m 中，本质不同的字符串长度种数为 \mathcal{O}(\sqrt{n}) 级别。

\bf{Proof\space 1}

考虑 s_1\sim s_m 种出现了 k 种本质不同的长度，从小到大依次是 \text{len}_1\sim \text{len}_k，记 \text{cnt}_i 表示第 i 种长度的出现次数，形式化地，\text{cnt}_i=\sum\limits_{j=1}^m[|s_j|=\text{len}_i]。

那么有：\sum\limits_{i=1}^k(\text{len}_i\cdot \text{cnt}_i)=n。

可以发现 \text{len}_i\ge i,\text{cnt}_i\ge 1。后面那个很显然，因为这种长度出现时一定存在一个字符串满足其长度为 \text{len}_i。

至于前面那个使用归纳法证明：

• 当 i=1 时 \text{len}_1\ge 1 显然成立。

• 假设对于 i\in[1,p]\cup\mathbb{Z} 时成立，则对于 i\in[1,p+1]\cup\mathbb{Z} 时，由于 \text{len}_1\sim \text{len}_k 中的每一个数都是一种本质不同的长度，且从小到大排列，所以 \text{len}_{p+1}>\text{len}_p\ge p。由于都是整数，所以 \text{len}_{p+1}\ge p+1。

由于这里涉及到的量都是正的，所以 \text{len}_i\cdot \text{cnt}_i\ge i，因此 \sum\limits_{i=1}^ki\le \sum\limits_{i=1}^k(\text{len}_i\cdot \text{cnt}_i)=n，因此有 \dfrac{k^2+k}{2}\le n。可以得到 k\le \sqrt{2n}=\mathcal{O}(\sqrt{n})。注意这里不是在解不等式，由 \dfrac{k^2+k}{2}\le n 推导出一个成立的条件。

证毕。

那么我们可以对于这 \mathcal{O}(\sqrt{n}) 种长度分别求解。在求解一种长度 \text{len} 的询问时，我们对于每个点 u 预处理 \text{str}(u,\text{anc}(\text{len},u)) 和 \text{str}(\text{anc}(\text{len},u),u) 的哈希值 \text{uk}_u 和 \text{dk}_u（若不存在则不处理）。需要先预处理 \text{up}_u 和 \text{dwn}_u 表示 \text{str}(u,1) 和 \text{str}(1,u) 的哈希值。容易得到：

• \text{up}_u\equiv \text{up}_{\text{fa}_u}+\text{val}_u\cdot \text{base}^{\text{dep}_u-1}\pmod{ \text{MOD}}
• \text{dwn}_u\equiv\text{dwn}_{\text{fa}_u}\cdot \text{base}+\text{val}_u\pmod{ \text{MOD}}

由于这个做法比较垃圾，我们不能在求解每种长度时重新遍历树计算哈希值，否则会超时。可以考虑牺牲空间，在第一次遍历树时就对于每个点存下这些哈希值。这样可以省去 \mathcal{O}(\sqrt{n}) 次遍历树的时间。

• \text{dk}_u\equiv \text{dwn}_u-\text{dwn}_{\text{anc}(\text{len},u)}\cdot \text{base}^{\text{len}}\pmod{\text{MOD}}

可以预处理 \text{base} 的若干次方以及对应的逆元。考虑怎么快速求 \text{anc}(\text{len},u)。由于查询次数为 \mathcal{O}(n\sqrt{n})，所以单次查询必须为 \mathcal{O}(1)。可以考虑维护 1\rightsquigarrow u 构成的序列 \text{stk}，使得 \text{stk}_i 为路径上的第 i 个点。则所求即为 \text{stk}_{\text{dep}_u-\text{len}}。每次遍历到一个点 u 时，将 u 加入序列末尾。结束 u 的遍历时，将 u 从序列末尾删除。

在求解每种长度时再考虑对于每种询问串的哈希值 \text{hsh} 单独求解。考虑记 \text{num}_{0,u} 表示 1\rightsquigarrow u 上有多少个点 v 满足 \text{uk}_v=\text{hsh}，\text{num}_{1,u} 表示 1\rightsquigarrow u 上有多少个点 v 满足 \text{dk}_v=\text{hsh}。这个可以考虑从 1 到 n 扫描 i，依次维护 v\in[1,i] 的情况，则每次新扫到一个位置，需要修改（+1）的值拍平成 \text{dfn} 序后形如一段区间。

至于询问，对于 x\rightsquigarrow \text{lca}(x,y) 那条链上的贡献，考虑匹配的起点在哪个位置，容易发现链上的一个点 u 能够匹配当前询问串当且仅当 \text{dep}_u-\text{dep}_{\text{lca}(x,y)}\ge \text{len}，且 \text{uk}_u=\text{hsh}。因为这样才能包含在直链内。进一步发现满足这个条件的点位于 x\rightsquigarrow \text{anc}(\text{dep}_x-\text{len}-\text{dep}_{\text{lca}(x,y)},x) 上，那么拿 \text{num}_{0,x} 和 \text{num}_{0,\text{anc}(\text{dep}_x-\text{len}-\text{dep}_{\text{lca}(x,y)},x)} 差分即可。\text{lca}(x,y)\rightsquigarrow y 的查询方式类似，注意此时匹配的方向是自上而下，用 \text{num}_1 值差分计算。

此时，一共有 \mathcal{O}(n\sqrt{n}) 次修改，\mathcal{O}(n) 次查询，维护以 \text{dfn} 序为下标的差分数组，那么只需要分块支持 \mathcal{O}(1) 单点修改，\mathcal{O}(\sqrt{n}) 前缀查询即可。

值得注意的是，为了将同种哈希值的询问一起做，考虑使用排序将它们排在一个连续的区间内时，需要使用基数排序确保排序复杂度线性，才能保证 \boldsymbol{\mathcal{O}(\sqrt{n})} 次排序的总复杂度为 \boldsymbol{\mathcal{O}(n\sqrt{n})}。

\bf {Case\space 2}：跨过直链的情况

考虑分别处理每种串 s_k 的询问。

假设跨过直链的匹配发生在 u\rightsquigarrow v 上，其中 u,v 是 x\rightsquigarrow y 上的节点且 u 在 v 前。此时一定满足，\text{str}(u,\text{lca}(x,y)) 是 s_k 的前缀，\text{str}(\text{lca}(x,y),v) 是 s_k 的后缀。

同时，\text{str}(u,\text{lca}(x,y)) 是 \text{str}(x,\text{lca}(x,y)) 的后缀，\text{str}(\text{lca}(x,y),v) 是 \text{str}(\text{lca}(x,y),y) 的前缀。

考虑找到最长的长度 P,Q，使得 \text{str}(x,\text{lca}(x,y)) 存在长度为 P 的后缀为 s_k 的前缀；\text{str}(\text{lca}(x,y),y) 存在长度为 Q 的前缀为 s_k 的后缀。

考虑一个基础问题：

给出字符串 a,b，找到 b 的最长前缀使得它是 a 的后缀。求出这个最长长度。

解决方法是：找到 a 的一个后缀 a[i,|a|] 使得 |\text{lcp}(a[i,|a|],b)| 最大。记 L=|\text{lcp}(a[i,|a|],b)|，则 a[i,|a|] 最长的长度不超过 L 的 \text{border} 的长度即为所求。

接下来证明正确性。

\bf {Proof\space 2}

首先，这个 \text{border} 一定是同时是 b 的前缀和 a 的后缀。因为它是 a[i,|a|] 的前缀又是它的 \text{border}，说明 a[i,|a|] 存在这个 \text{border} 作为后缀。自然 a 也存在这个 \text{border} 作为后缀。记这里求出来的长度为 \text{len}。

考虑是否存在更长的答案。假设存在更长的答案长度为 \text{tmp}，其一定不超过 L，不然 a[i,|a|] 就不是使得 \text{lcp} 长度更大的后缀了。此时，a[i,|a|] 与 b 存在长度为 \text{tmp} 的 \text{lcp}。这时候 a[i,|a|] 开头的 \text{tmp} 个字符形成的字符串与结尾的 \text{tmp} 个字符形成的字符串相等。此时 \text{tmp} 是 a[i,|a|] 的一个更长的、长度不超过 L 的 \text{border}，矛盾。

因此不存在更长的答案，\text{len} 即为所求。

证毕。

将原问题转化成上述形式，那么 P 就是 \text{str}(\text{lca}(x,y),x) 最长的前缀长度满足它是 s_k^R 的后缀。这个和原问题显然是等价的，因为两个询问串都是原问题询问串的反串。不妨令新问题答案为 w，则反过来后原串对应的位置也相等，原问题的答案至少为 w；若原问题存在更长的答案 z，则反串中这些对应的位置也相等，z 就是新问题的一个更长的答案，与 w 的定义矛盾。

因此，P 就是在这个基础问题中 b=\text{str}(\text{lca}(x,y),x),a=s_k^R 的情况；Q 就是在这个基础问题中 b=\text{str}(\text{lca}(x,y),y),a=s_k 的情况。

先对 s_k 以及 s_k^R 进行后缀排序。

最长的长度不超过 L 的 \text{border} 很好求，由于要求的是某个后缀的 \text{border}，在其反串上就变成了前缀的 \text{border}，这两个问题也是等价的，和上面的证明类似。

因此，对于 s_k 和 s_k^R 建立失配树 T_k 和 T_k^R，并进行轻重链剖分。找到满足条件的后缀后，先看一下它的反串对应的是哪一棵失配树，然后在失配树上一条一条重链向上跳。失配树的根链是单调递减的（从节点到根）。若链顶大于 L，就整条链跳过，否则在链上二分，单次询问时间复杂度为 \mathcal{O}(\log n)。

接着考虑如何找到使得 L 最大的后缀。这个后缀一定满足，它要么是 a 中最大的字典序大小不超过 b 的后缀，要么是 a 中最小的字典序大小个超过 b 的后缀。换句话说，设这两个后缀与 b 的 \text{lcp} 长度分别为 A,B，则 L=\max\{A,B\}。

接下来给出证明：

\bf{Proof\space 3}

设它们的排名分别为 i,j。则一定有 j=i+1。因为根据定义，排名为 i+1 的后缀字典序大小已经超过了 b，但是排名在 [1,i]\cup\mathbb{Z} 内的后缀字典序大小都不超过 b。

考虑反证，假设排名为 \text{rnk}(\text{rnk}\ne i\land \text{rnk}\ne i+1) 的后缀会得到更大的 \text{lcp} 长度。

记这个更大的 \text{lcp} 长度为 \text{len}。分两种情况讨论：

• 若 \text{rnk}\in[1,i)\cup\mathbb{Z}，则排名为 \text{rnk} 的后缀的前 \text{len} 位均与 b 的前 A 位相同。根据 \text{len} 的定义可知其第 A+1 位也与 b 的这一位相同。根据定义，排名为 i 的后缀的第 A+1 位小于 b 的这一位，或者说这一位不存在（空字符）。此时，排名为 i,\text{rk} 的两个后缀前 A 位相同都等于 b 的前 A 位。且后者的第 A+1 位大于前者的这一位。说明后者比前者字典序大，这与 \text{rnk}\in[1,i)\cup\mathbb{Z} 矛盾。

• 若 \text{rnk}\in(i+1,|a|]\cup \mathbb{Z}，与上一种情况类似推导得到字典序大小上的矛盾即可证明。

证毕。

于是考虑求得排名 i。由于经过后缀排序，即这些后缀的字典序递增，所以答案有单调性，直接二分这个排名即可。

考虑如何求一条链上的字符串和序列上的字符串的最长公共前缀长度。对原树进行轻重链剖分，将边权转化为深度较深的端点的点权，则这条链会被表示成 \mathcal{O}(\log n) 条连续的重链区间。对于 \text{dfn} 序列形成的字符串维护哈希，对 s_k 和 s_k^R 也维护哈希。

一条一条重链匹配，若能全部匹配上，就算上这些长度，否则二分第一个不同的位置。只有第一条不匹配的重链需要二分，因此时间复杂度为 \mathcal{O}(\log n)。

这部分细节比较多，尤其是一方匹配完的边界情况，具体看代码中的 qlcp 部分。

此时，这个过程已经求出了 \text{lcp} 长度，顺带比较一下大小配合套在外面的二分。

那么 P,Q 均被我们求出来了。

求出来之后，我们只需要考虑 x\rightsquigarrow \text{lca}(x,y) 的后 P 个位置为开头处形成的匹配，因为不能匹配 s_k 更长的前缀了。

记这 P 个位置依次为 u_1\sim u_P，满足它们按照 \text{lca}(x,y)\rightsquigarrow x 路径上的顺序排列；记后 Q 个位置依次为 v_1\sim v_Q，满足它们按照 \text{lca}(x,y)\rightsquigarrow y 路径上的顺序排列。

则 u_i 为开头处能形成合法的匹配，当且仅当一下三点同时满足：

证明：

\bf{Proof \space 4}

• 充分性：

  因为 i\ne |s_k|，所以跨过了 \text{lca}(x,y)。因为 s_k[1,P] 存在长度为 i 的 \text{border}，根据 P 的定义可以得到 \text{str}(u_i,\text{lca}(x,y))=s_k[P-i+1,P]=s_k[1,i]；因为 s_k^R[1,Q] 存在长度为 |s_k|-i 的 \text{border}，类似地，\text{str}(v_{|s_k|-i},\text{lca}(x,y))=s_k^R[1,|s_k|-i]，根据反串的定义得到 \text{str}(\text{lca}(x,y),v_{|s_k|-1})=s_k[i+1,|s_k|]。两者拼接恰好是 s_k。

• 必要性：

  若 u_i 开头处可以形成合法的匹配，首先一定有 i\ne |s_k|，因为要跨过 \text{lca}(x,y)。其次 \text{str}(u_i,\text{lca}(x,y))=s_k[1,i]，根据 P 的定义，\text{str}(u_i,\text{lca}(x,y))=s_k[P-i+1,P]，因此 s_k[1,i]=s_k[P-i+1,P]，即 s_k[1,P] 存在长度为 i 的 \text{border}；类似地，\text{str}(v_{|s_k|-i},\text{lca}(x,y))=s_k^R[1,|s_k|-i]=s_k^R[Q-|s_k|+i+1,Q]，因此 s_k^R[1,Q] 存在长度为 |s_k|-i 的 \text{border}。

证毕。

所以，我们要统计有多少 i 合法，就是要统计有多少 i 满足这三个条件。

转化成失配树上的限制，就是要求有多少 i 满足 i 在 T_k 中 P 的根链上，且 |s_k|-i 在 T^R_k 中 Q 的根链上。

考虑离线 + 扫描线。对于所有 s_k 的询问，将它挂在 T_k 的 P 节点上。考虑深度优先搜索 T_k，在过程中一并维护数组 a_0\sim a_{|s_k|}。其中 a_j 表示有多少 i，满足：

则只要在 P 处单点查 a_Q 即可。

每次新扫到一个点 u，则和上一层深搜相比根链上增加了一个点 u 的贡献。考虑 |s_k|-u 的贡献，此时首先满足 u\ne |s_k|，发现只有它子树内的点的根链经过它，即只要这些点的 a_j 值要增加 u 的贡献。拍平成 \text{dfn} 序后将 a 映射过去，再进行差分，则需要支持的操作形如区间加、单点查，由于此处修改、询问同阶，树状数组维护即可。每次结束一个点的深搜时，删去它的贡献。

这部分就做完了，时间复杂度为 \mathcal{O}\left(n\log^2 n\right)。

综上，这个做法时空复杂度均为 \mathcal{O}(n\sqrt{n})，可以接受。前面也说过空间可以做到线性，只是需要一些精湛的卡常技艺。

AC Link & Code

参考资料

• 字符串基础

  作者：@Alex_Wei

• OI WiKi 后缀数组简介

• 本文涉及到题目的题解区。