尝试先认(随)真(便)口胡一些经典问题。

前置技能

Height

定义

\text{Height}(i) = |\text{LCP}(\text{Suffix}(\text{sa}(i)), \text{Suffix}(\text{sa}(i - 1)))|

用后缀树来解释就是,dfn 第 i 大的终止节点和第 i - 1 大的节点的 LCA 所代表的子串的长度(深度)。\text{Height}(1) = 0

怎么求?

引理

\text{Height}(\text{rk}(i)) \geq \text{Height}(\text{rk}(i - 1)) - 1,即第 i 个后缀的 \text{Height} 至少为前一个后缀的 \text{Height} 减一。

证明

考虑后缀 i - 1 在 dfn 序上的前驱,记为后缀 j - 1

根据定义 j - 1i - 1 的 LCP 的长度就是 \text{Height}(\text{rk}(i))

如果 j - 1 < |S| - 1,这意味着 j - 1 不是最后一个后缀,那么 j - 1 的下一个后缀 ji - 1 的下一个后缀 i 的 LCP 长度至少为 \text{Height}(\text{rk}(i - 1)) - 1

否则 j - 1 = |S| - 1,即为最后一个后缀,那么 \text{Height}(\text{rk}(i)) = 0 \leq \text{Height}(\text{rk}(i - 1)) - 1

得证。

实现

有了上面这个引理,我们可以在 O(n) 的时间内求出 Height。

考虑枚举一下 i,然后求 \text{Height}(\text{rk}(i))。我们记录上一个 i 的值,然后从上一个 i 的值 -1 开始,暴力匹配后缀 i\text{sa}(\text{rk}(i) - 1)(dfn 序上的前驱)。

\text{Height} 的值减少 n 次,最多不超过 n,因此复杂度 O(n)

int tmp = 0;
REP(i, N) {
    if (tmp) tmp--;
    if (rk[i] == 1) continue;
    while (str[i + tmp] == str[sa[rk[i] - 1] + tmp]) tmp++;
    height[rk[i]] = tmp;
}

SAM 的拓扑序

我们知道 SAM 的 DAWG 是个 DAG,因为如果存在转移 \delta(u, c) = v,那么 |\max(u)| < |\max(v)|,因此直接按照等价类的 \max 进行一趟排序就可以知道拓扑序了。由于值域是 O(n) 的,直接计数排序即可。

SAM 的 PT 和后缀树

SAM 的 PT 是其母串的反串的后缀树经过缩点得到的。

广义后缀自动机 (Generalized Suffix AutoMaton, GSAM)

考虑有一棵 Trie,GSAM 能够接受所有 Trie 的后缀,即从某个节点出发走向其后代中的某个叶子节点形成的串。

正确的构造方法是,考虑 bfs 构造。维护一个 tpos[i] 表示 Trie 上第 i 个节点在 SAM 中的位置。每次我们取出队头,以其父节点的 tpos 作为 SAM 构增量造中的 lst 进行插入即可。

这样构造复杂度一定是线性的。

Easy

E1 求任意两个子串的 LCP

求子串 LCP 就是求两个子串开头的后缀的 LCP。所以这个问题就是求两个后缀的 LCP。

SA

假设两个后缀是 i, j\ (\text{rk}(i) < \text{rk}(j))

考虑在后缀树上,就是两者的 LCA。然后我们按照 dfn 一个一个向右求 LCA,最后的答案就是两者的 LCA。所以就是

\min_{k = \text{rk}(i) + 1}^{\text{rk}(j)} \text{Height}(k)

这就是个 RMQ。ST 表即可。

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

SAM

得先建个反串,现在问题是两个前缀的 LCS(最长公共后缀)。

先处理出 \text{idx}(i) 表示前缀 i 所在的节点。方法为,每次加入的时候记录一下(就是代码中的 last 开个数组存)。

然后在 Parent 树上求 \text{LCA}(\text{idx}(i), \text{idx}(j)),这个等价类的 \max 就是两者的 LCS。很容易证明。

O(n) - O(\log n)

E2 比较两个子串的字典序

就是 LCP。

E3 本质不同子串个数

SA

总的个数 - 重复的串的个数。

总的个数显然是 \binom {n + 1} 2,那么重复的串的个数呢?

考虑增量,按照 dfn 序从小到大加入一个后缀 i,并计算后缀 i 的哪些前缀,会和之前的后缀的哪些前缀相同。

发现只需要计算这个后缀的 dfn 序前驱后缀 j 和后缀 i 的重复即可。因为如果有后缀 k \neq ji 有某个共同前缀 T,那么 ji 也必定有共同前缀 T,因此在加入 j 的时候这个 T 已经被减去了。

ji 的共同前缀个数,就是 LCA 深度、LCP 长度、\text{Height}(\text{rk}(i))

因此本质不同子串个数就是 \binom {n + 1} 2 - \sum_{i = 2}^n \text{Height}(i)

O(n)

SAM

做法 1 利用 PT

就是后缀树有多少个节点。

我们的 PT 就是缩点后的后缀树,然后对于等价类 u,一共有 |\max(u)| - |\min(u)| 个节点被缩到了这里。因此对于所有等价类求和 |\max(u)| - |\min(u)| 即可。

复杂度 O(n)

做法 2 利用 DAWG

考虑每一个子串唯一对应一条从 s_0 出发的路径。

所以就是求这个 DAG 的路径条数。

d_u 表示从节点 u 出发有多少条路径。那么我们拓扑序倒序地来搞,有

d_u = 1 + \sum_{\exists c, \delta(u, c) = v} d_v

第一项就是停留在 v,后面的是往后走的方案数之和。

那么答案就是 d_{s_0} - 1,因为不能停留在 s_0,所以要 -1

复杂度 O(n)

E4 本质不同子串长度和

SA

假设有一个函数 f(x) 表示长度为 x 的串的所有子串和,不要求本质不同。

还是考虑总长度和 f(x) 减去重复的串的长度和,仍然是增量法,按字典序加入一个后缀,并减去那些已经出现过的前缀。

这些前缀必定就是上一个字典序和自己重复的串。长度和就是 f(\text{Height}(i))。减一下就好。

复杂度 O(n\log n),取决于 SA 的复杂度。

SAM

做法 1 利用 PT

考虑后缀树的每个节点的贡献就是自己的长度。

我们的 PT 就是缩点后的后缀树,然后对于等价类 u,一共有 |\max(u)| - |\min(u)| 个节点被缩到了这里,并且每一个串的贡献就是自己的长度。因此对于所有等价类求和 \displaystyle\sum_{i = |\max(u)|}^{|\min(u|} i 即可。

复杂度 O(n)

做法 2 利用 DAWG

考虑每一个子串唯一对应一条从 s_0 出发的路径,并且贡献就是路径长度。

所以就是求这个 DAG 的路径长度和。

d_u 表示从节点 u 出发有多少条路径。处理方法如上个问题

d_u = 1 + \sum_{\exists c, \delta(u, c) = v} d_v

再设 c_u 表示从 u 出发的路径长度和,那么

c_u = \sum_{\exists c, \delta(u, c) = v} c_v + d_v

对于每一条路径,加入一个点之后长度贡献会多 1,然后一共有 d_v 条路径可以加,因此加上 d_v

复杂度 O(n)

E5 字典序第 k 大子串-本质不同/TJOI2015 弦论 第一问

SA

我们考虑让所有后缀按字典序排序,那么没加入一个后缀,以及这个后缀所包含的新的前缀,一定就是 \text{Height} + 1 到自己的长度这一部分。因为这些部分一定都是新的,且是字典序最小的,所以直接和 k 做比较即可。

SAM

先处理出 d 之后,直接看哪个转移会消耗殆尽 k,直接走进去就好。

复杂度 O(n)

E6 最小循环位移

SA

直接倍长做后缀排序,第一个字典序在左半部分的后缀就是答案。

复杂度 O(n\log n),取决于 SA 的复杂度。

SAM

倍长建 SAM,每次走最小的转移。走 |S| 次。

时间复杂度 O(n)

E7 子串出现次数

给出母串 S 与模式串 T,求 TS 中的出现次数。

SA

对串 S + \star+T 进行后缀排序,然后我们找到 T 作为后缀的位置,向左右二分出最远的距离,满足这个区间的 \min\text{Height} \geq |T|,表示 T 完全出现过。然后这个区间的大小就是出现次数。

O((|S| + |T|)\log (|S| + |T|))/O(|S| + |T|)

SAM

实际上就是运行完 T 到的节点的 \text{endpos} 大小,我们想想怎么对于每个等价类 u 处理其 \text{endpos} 的大小 \text{cnt}(u)

这个过程在构建玩 SAM 之后进行。

我们令每一个前缀运行完到的节点的 \text{cnt}(u) \leftarrow 1,然后在 PT 上求一个子树和即可。

为什么是对的?考虑到 PT 上节点 u 的所有儿子的的 \text{endpos}u 的拆分这个事实,正确性就很显然了。

然后处理完之后直接运行 T 即可。

复杂度 O(|S| + |T|)

E8 求覆盖任意位置最短的只出现一次的串

即,对每个位置 i,求出最小的 l,使得存在 T = \text{substr}(j, j + l),满足

  • |\text{endpos}(T) |= 1
  • j \leq i < j + l

SAM

考虑先处理出每一个 |\text{endpos}| = 1 的状态 u 以及其对应的,\text{endpos} 中唯一的元素的值 x。那么我们会发现在这个状态中的所有字符串,是一个阶梯状的。即对于长度等于 \max(\text{link}(u)) + 1 的那个串,他会覆盖 [x - \max(\text{link}(u)), x] 这部分。当然还有一些串没有被这个串覆盖到,而是被更长的串,以一个公差为 1 的等差数列的形式覆盖。即对于 i \in [x - \max(u), x - \max(\text{link}(u)) - 1],他会被长度为 x - i + 1 的串覆盖。为了使这个船的长度最小,我们让 x 最小即可。

所以对于这两部分都开一个线段树,第一个线段树维护最小值,第二个线段树维护 x 的最小值即可。

时间复杂度 O(n\log n)

E9 在对 S 建的 SAM 中,快速定位 S 的某个子串

SAM

假设定位 \text{substr}(i, j),我们先处理出所有前缀所在的位置,这个可以在插入的时候就办到。

现在我们发现,\text{substr}(i, j)\text{pre}(j) 的一个后缀,因此一定在 PT 上 \text{pre}(j) 到根的链上。所以直接倍增,直到 \text{substr}(i, j) 的值落在了合适的区间即可。

单次复杂度 O(\log n)

E10 求任意两个后缀 LCP 之和

\sum_{0 \leq i, j < |S|} |\text{LCP}(\text{suf}(i), \text{suf}(j))|

SA

考虑用 \text{Height} 计算两个串的 LCP 的做法就是区间 \min。那么我们考虑贡献,对于每个 \text{Height} 单调栈处理出左右极长最值区间即可。然后算贡献。

时间复杂度 O(n\log n),取决于后缀排序的复杂度。

SAM

首先你得倒着建 SAM,因为这题我们不用 DAWG,只用 PT(实际上是 Suffix Trie)。

枚举一个状态,然后计数,看不同子树中选两个后缀点的方案数即可。

时间复杂度 O(n)

E11 两串 LCS

SA

分隔符,拼接,后缀排序,枚举位置,看左右第一个来自不同串的后缀的 LCS 即可。这个过程可以正反两次做一下。

时间复杂度 O(n \log n),取决于后缀排序的复杂度。

SAM

假设两个串分别是 S, T,对 S 建 SAM。考虑计算 T 的每一个前缀,求一个最长的后缀满足是 S 的子串。

假设我们已经求出了 \text{pre}(T, i) 的答案 \text{substr}(T, j, i),现在想求 \text{pre}(T, i + 1) 的答案。容易看出新的答案的左端点必定不可能在老的答案的左端点左侧。那么我们只需要不断在 PT 上遍历 \text{substr}(T, j, i) 所在状态到根的链,即其所有的后缀,这个遍历是让 j 向右走,直到有一个为 S(i) 的出边为止,有的话就走进去。走进去之后就找到了这个前缀的答案。

容易发现我们挪动 ji 的次数都不会超过 n 次,每次复杂度是 O(1) 的,因此为线性的复杂度。

Medium

M1 SCOI2012 喵星球上的点名

你有 n 个名字,每个名字由两个串组成,分别为姓和名。

会进行 m 次点名,每次点名给出一个串 T。对于第 i 个名字,如果满足 T 是这个名字的姓或名的子串,那么称这次点名关联第 i 个名字。

你需要回答:

  • 每次点名关联了多少个名字?
  • 每个名字被多少次点名关联?

n \leq 20000, m \leq 50000,名字串长,点名串长各自不超过 \leq 100000,字符集大小 10^4

SA

把所有串,包括点名的串弄到一起,然后求 SA 和 Height。

枚举一个点名的串,在 Height 上左右二分出能完全匹配自己的位置,记录下来。

现在我们知道一个点名的串会有哪些串来匹配,我们想知道这些串对答案的贡献。具体而言,考虑给每个串一个颜色,颜色对应于是哪个名字的后缀。当然如果这个串是点名的串那么没有颜色。现在对于每一个点名串,第一问就是求一个区间颜色个数。

那么直接考虑莫队。

第二问呢?我们发现在莫队的时候,对于每个颜色维护一个 lst[i] 表示这个颜色上一次“出现”(出现次数从 0 变成 1)的“时刻”(第几个询问),每次更新出现次数时,如果一个颜色又“消失了”(出现次数从 1 变成 0),那么就将这个颜色的第二问加上这段时刻的长度。这样就处理了第二问。

时间复杂度 O(n\log n)

SAM

对所有名字串建广义后缀自动机。

然后对于每个点名的串 T,先运行这个串。那么这个串关联的名字,一定存在某个后缀,满足 T 是这个后缀的前缀。

我们知道 SAM 的 PT 是反串后缀树缩点得到的,那么如果 T 是某个串的前缀,则 T 必定在 PT 上是某个串的祖先。

因此我们要求的就是,这个串的后代里面的颜色个数。

dfs 序+和 SA 同样做法的莫队即可。

code

M2 第 k 小子串,子串重复贡献,且多组询问

SAM

考虑处理出每个节点的 \text{endpos} 以及 d,注意这里的 d_u 的意思是从 u 出发的所有路径的所到达的点的 \text{endpos} 之和。

然后一次询问我们可以最大 O(n) 的、和 E5 的做法类似地来做。现在考虑怎么多组询问。

称 DAWG 上一个点的出点中,d 最大的点为其“重儿子”,其余点为“轻儿子”,那么我们发现 DAWG 被剖成了若干个重链。考虑在 O(n) 的暴力转移中,如果在某一个节点,我们走向了一个轻儿子,那么 k 至少减去一半。因此我们最多走 \log k 次轻儿子。对于走重儿子,我们考虑倍增。设 t(u, k) 表示从 u 出发,走 2^k 次重儿子,k 会减少的值(会跳过多少个子串,处理方式是先处理 k =0 时,值就是所有 \delta 比自己小的出边的 d 的和,然后倍增时加上两个部分即可),那么我们可以直接倍增。

每次倍增是 O(\log) 的,会进行 O(\log^2) 次。

如果要输出方案,由于我们在跳的时候可以方便维护答案的长度,又知道终止于哪个状态,因此只需要输出这个状态的某个后缀即可。

M3 一道神奇的题

给定多个串 s_1, s_2 \cdots s_n,你需要在每个串中选出一个可以为空的子串,将它们拼接起来。求出可以得到的本质串的个数,模 998244353

|\sum s_i| \leq 10^6,字符集 26

SAM

考虑如果你得到了一个串,判断这串是否能够被拼接出来的方式就是,拿 s 依次去扫,然后贪心尽量匹配这个串。

我们对于每个串各自建 SAM,这个过程就是,假设某个串的 SAM 的某个点没有 c 的出边,那么我们就需要转移到这个串后面的一个串的 SAM 的节点上,满足这个节点刚好是 c 这个字符对应的节点。

我们显式地连出这条边,显然,连了之后,仍然是一个 DAG。并考虑在此之上进行 dp,求出路径个数即可。

时间复杂度 O(n|\Sigma|)

M4 SAM 上线段树合并

SAM

给定一个串 S,每次询问 \text{substr}(i, j)\text{substr}(x, y) 中的出现次数。

首先我不会线段树合并

如果我们能直到 \text{substr}(i, j) 所在状态的 \text{endpos} 即可,那么这就是数有多少个数在 [x + j - i, y] 中的区间询问。

考虑讲所有询问离线,然后用线段树合并来维护这个过程。

对每个状态开一个权值线段树,那么我们发现一个状态在 PT 上的儿子们的权值线段树,合并起来就是自己的 \text{endpos}。怎么合并呢,看下面这个代码:(source:styx)

然后区间查就是基本操作了。

int merge(int a,int b,int l,int r)
{
    if(!a) return b;
    if(!b) return a;
    if(l==r)
    {
        //按照所需合并
        return a;
    }
    int mid=(l+r)>>1;
    tr[a].l=merge(tr[a].l,tr[b].l,l,mid);
    tr[a].r=merge(tr[a].r,tr[b].r,mid+1,r);
    push_up(a);
    return a;
}

就完了。

复杂度是单次合并 O(\log n) 的,因为两个儿子的权值线段树没有交,所以肯定是“一下就没了”。

M5 n 个串 LCS

n \leq 10

SAM

做法 1 GSAM

直接建出 GSAM,然后考虑每个状态状压一下自己在 PT 树上的后代是否存在某个串的前缀点,最深的,所有串的前缀点都有的就是答案。

做法 2 SAM

对串 S_1 建 SAM。

我们考虑拿 S_{2\cdots n} 来进行上面说的,两个串 LCS 的过程,并且我们需要对 SAM 的每个状态 u 维护一个 \text{len}(u, i) 表示,u 所对应的串,在第 i 个串中出现过的最长后缀。那么对于每个状态,其 \text{len} 的最小值就是以这个状态对应串为结尾的 LCS 的长度。对于所有点取 \max 即为答案。

考虑怎么维护这个东西。

首先在一个串进行 LCS 的过程中,维护一下当前匹配的最长后缀长度,跳 PT 树将就这个值置为新的状态的 \max,走 \delta 就让这个值加 1,然后对每一个到的状态维护 \text{len}

但是有一个大问题,我们更新一个点的 \text{len},实际上应该更新的是这个点到根的所有 \text{len},因为这些点都可以匹配。但是我们也不能每次都遍历一下,所以只能先放在底部,最后上传 \text{len}

OI-字符串-SAM后缀自动机 OI-字符串-SA后缀数组

fhq-Treap 速查笔记
上一篇 «
字符串学习笔记总览
» 下一篇