Znzryb's Blog
0%

2026牛客暑期多校 8——E-Prefix Codes

Posted on Edited on

题目大意

前缀码

时间限制： C/C++/Rust/Pascal 2秒，其他语言4秒

空间限制： C/C++/Rust/Pascal 1024 M，其他语言2048 M

在这道题目中，码字（codeword）指一个非空字符串，码本（codebook）指一个由若干互不相同的码字组成的非空集合。

如果一个码本中任意两个不同的码字 xx 和 yy，都满足 xx 不是 yy 的前缀，且 yy 也不是 xx 的前缀，则该码本被称为前缀码（prefix code）。

Soy 得到了两个非空字符串 ss 和 pp。他想使用 ss 的子串作为码字来构造一个前缀码。但是，他不希望 pp 在任何码字中出现。

更正式地说，如果一个字符串 xx 满足以下所有条件，则它是一个合法的码字：

  • xx 是非空字符串；

  • xx 是 ss 的一个子串；

  • pp 不是 xx 的子串。

子串仅通过其字符串内容进行区分。如果同一个字符串在 ss 的多个不同位置出现，它仍然只被视为一个合法的码字。

一个有效的码本指完全由合法码字组成的前缀码。换句话说，它是一个由合法码字组成的非空集合 CC，使得对于集合中的任意两个不同字符串 x,y∈Cx, y \in C，互不为对方的前缀。

如果两个有效码本中，存在一个码本包含某个码字而另一个码本不包含，则认为这两个码本是不同的。

请计算 Soy 能构造出多少种不同的有效码本。由于答案可能非常大，请将结果对 998244353998244353 取模后输出。

第一行包含一个字符串 ss（1≤∣s∣≤5⋅1051 \le \vert{}s\vert{} \le 5 \cdot 10^5）。

第二行包含一个字符串 pp（1≤∣p∣≤5⋅1051 \le \vert{}p\vert{} \le 5 \cdot 10^5）。

保证两个字符串均仅由小写英文字母组成。

输出一个整数，表示不同的有效码本数量对 998244353998244353 取模后的结果。

在样例中，s="aba"s = \text{"aba"} 的子串包含 a, b, ab, ba, aba。其中包含 p="ba"p = \text{"ba"} 的子串有 ba 和 aba。

剔除掉包含 pp 的子串后，合法码字的集合为：{"a", "b", "ab"}。

利用这些合法码字构成的有效码本（即集合内的码字互不为前缀）如下：

  1. {"a"}

  2. {"b"}

  3. {"ab"}

  4. {"a", "b"}

  5. {"b", "ab"}

注意：{"a", "ab"} 不是有效码本，因为 "a" 是 "ab" 的前缀。

因此总共有 55 种不同的有效码本。

思路讲解

注意，使用 endpos 集合对这个字符串的子串进行分组啊，而不是反过来。

可以看到 BB 和 ABB 的 endpos 集合相同，所以被放在了同一个 SAM 节点啊

这个是自动机：

image

这个是 link 树：

image

一开始的时候（即刚遍历完 ab 的时候） b 和 ab 显然是处于同一个节点中。

image

然后读入到第三个字符 ‘b’ 的时候，b 和 ab 就要分道扬镳了。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 定义后缀自动机的最大状态数，通常是字符串长度的两倍
const int MAXLEN = 200005;

// 后缀自动机节点结构
struct State {
    int len;              // 该状态包含的最长子串的长度
    int link;             // 后缀链接，指向包含当前状态最短子串的最长真后缀的状态
											    // （把最短子串的第一个字母去掉，也就是所谓的最长真后缀）
    int next[26];         // 字符转移边，假设字符集为小写字母 a-z
};

State st[MAXLEN * 2];
int sz;                   // 当前自动机中的状态总数
int last;                 // 指向当前整个字符串完整前缀所在的状态

// 初始化后缀自动机
void sam_init() {
    // 状态 0 是初始状态，代表空串
    st[0].len = 0;
    st[0].link = -1;
    for (int i = 0; i < 26; ++i) {
        st[0].next[i] = -1;
    }
    sz = 1;
    last = 0;
}

后缀自动机的重要性质

这些性质乍看之下非常简单啊，但是务必事先清楚，否则之后可能会看不懂一些东西啊。

核心定理：同一个状态里的字符串，长度必定是绝对连续的
在 SAM 中，如果状态 VV 里包含了一个短字符串 SS 和一个长字符串 LL，那么介于它们长度之间的所有后缀，必须全部都在状态 VV 里**，绝对不可能有断层。为什么？（反证法）**
假设状态里有长度为 3 的串和长度为 5 的串（它们在原串中出现的集合 endposendpos 是一模一样的，比如都出现了 4 次）。
那么长度为 4 的那个后缀，它的出现次数绝不可能超过 4 次（因为它包含长度为 5 的串），也绝不可能少于 4 次（因为它被长度为 3 的串包含）。
所以长度为 4 的串，出现集合也必定完全一样！它必须乖乖待在同一个状态里。

前提：同一个状态里的所有字符串，它们的结束位置集合（endposendpos）是完全一模一样的。

推导：假设我们在原字符串中随便挑一个它们的共同结束位置，比如位置 P。

结论：既然结束位置固定在了 P，如果你要在这个位置截取一个长度为 L 的字符串，你只能往前数 L 个字符。位置一旦固定，长度一旦固定，切出来的字符串必然是唯一确定的**！**

在 SAM 中，任何一条转移边 u --(c)--> v 的构建，都必须且只能遵循唯一一条规则：
字符串 maxstr(u)+cmaxstr(u) + c 的 endposendpos 集合，必须等于状态 vv 代表的 endposendpos 集合。

image

插入字符，构造后缀自动机：函数 sma_insert()

插入一个后缀字符 cc，我们到底要修改什么，其影响范围是什么？

只有新字符串的“后缀”们，它们的 endposendpos 才会新增 LL。 其他任何子串的 endposendpos 都不变。

所以我们要对所有的新字符串的后缀进行修改。

新字符串即：比如说，abaababaab，遍历到了 abaaabaa， 最后的 bb 还没遍历到，abaaabaa 就是我们的新字符串。

建立新字符串对应的 State 节点

这个就是平平无奇的这个初始化啊。相当于 new 一个下标为 cur 的这个节点啊，代表目前整个后缀字符串啊。（比如说，abaababaab，遍历到了 abaaabaa， 最后的 bb 还没遍历到，abaaabaa 的这个长度为 4 啊）

1
2
3
4
5
6
sz++;
int cur = sz;
st[cur].len = st[last].len + 1;
for (int i = 0; i < 26; ++i) {
	st[cur].next[i] = -1;
}

2. 更新旧后缀的转移边

1
2
3
4
while (p != -1 && st[p].next[c - 'a'] == -1) {
    st[p].next[c - 'a'] = cur;
    p = st[p].link;
}

此时我们要把之前字符串的所有后缀都加上字符 cc，让它们变成新字符串的后缀。

我们通过 link 链不断回溯 lastlast 的各个后缀状态 pp：

  • 如果 pp 没有字符 cc 的转移边，说明这个后缀加上 cc 后形成的新子串以前从未出现过（即 maxstr(p)+‘c’maxstr(p) + ‘c’ 对应的字符串后缀之前没有出现过啊（maxstr(p)maxstr(p)，就是状态 p 所包含的最长子串，++ 是指的字符串与字符拼接）），我们直接给它连一条边指向 curcur。

  • 如果回溯过程中遇到了一个状态 pp 已经有了 cc 的转移边，说明从这个长度开始的后缀加上 cc 形成的子串，在之前的字符串里已经出现过了，循环终止。

  • 如果我们强行继续更新下面的，由于不是新子串，我们不能够保证这个任何一条转移边 u --(c)--> v 必须满足：字符串 maxstr(u)+cmaxstr(u) + c 的 endposendpos 集合，必须等于状态 vv 代表的 endposendpos 集合。

3. 处理后缀链接 (核心难点，分三种情况)

1
2
3
if (p == -1) {
    st[cur].link = 0;
}

如果一直回溯到了虚拟边界（p=−1p = -1），说明字符 cc 以前压根就没出现过。新状态 curcur 没有其它真后缀曾在图中出现，它的后缀链接直接指向根节点（状态 00，代表空串）。

1
2
3
4
5
6
7
8
int to = st[cur].next[c - BASE];
// to 可以作为我们的 link 啊
// 但是我们需要其为最小串的这个去掉首字母以后的串啊
if (st[p].len + 1 == st[to].len) {
	// （p 是字符串）p + ‘c’ 就是 to 中的最长子串，因此不需要对这个 to 进行这个分裂
	// 根据 end pos 性质，to 中更短的，也是这个 cur 的这个后缀啊
	st[cur].link = to;
}

状态 pp 是我们找到的第一个拥有 cc 转移边的状态，它转移到了 toto。

如果 st[p].len+1==st[to].lenst[p].len + 1 == st[to].len，说明 toto 状态恰好只包含我们需要的那部分后缀（没有比它更长的了，如果有比这个 maxstr(p)+cmaxstr(p) + c 更长的啊，就麻烦了，因为我们保证 maxstr(p)+cmaxstr(p) + c 这个是 curcur 的后缀，但是更长的，就一定不是 curcur 的后缀了）。这是一种完美的平滑过渡，toto 理所当然地成为了 curcur 的后缀链接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
} else {
	sz++;
	int clone = sz;
	st[clone].link = st[to].link;
	st[clone].len = st[p].len + 1;
	for (int i = 0; i < 26; ++i) {
		st[clone].next[i] = st[to].next[i];
	}
	while (p != -1 && st[p].next[c - BASE] == to) {
		// 原先的，转移到 to 已经不合适了
		// maxstr(p) + c 的这个 endpos 包含 cur
		// 但是原来的 to 是不包含 cur 的，因此需要更新
		// 更新为这个这个 clone，因为 clone endpos 包含这个 cur
		st[p].next[c - BASE] = clone;
		p = st[p].link;
	}
	st[cur].link = clone;
	// 使用连续性定理（后缀自动机的性质里面提到的），我们知道 to 中包含 len(maxstr(p))+2 的这个字符串啊
	// 因此也接到这个 clone 上面啊
	st[to].link = clone;
}

这是 SAM 构造中最精妙的部分。如果 st[p].len+1<st[to].lenst[p].len + 1 < st[to].len，说明出现了断层。

  • 为什么会这样？ toto 状态原本代表了多个不同长度的子串。由于当前追加了新字符 cc，toto 中较短的那部分子串成为了新字符串的后缀（它们的出现位置集合 Endpos 增加了当前字符串的末尾），而 qq 中较长的那部分子串由于前面字符对不上，没有成为新字符串的后缀。

  • 怎么解决？ 同一个状态里的子串 Endpos 集合必须完全一致，现在它们分道扬镳了，所以必须把 toto 拆开。

  • 克隆操作：

    1. 新建一个 cloneclone 状态，专门用来存放原本 toto 中较短的、成为了当前后缀的子串。所以它的长度严丝合缝地设为 st[p].len+1st[p].len + 1。
    2. cloneclone 继承 toto 的所有出边和后缀链接（因为它本质上是 toto 的一部分，后续可以接的字符是一样的）。
    3. 我们把 toto 和新状态 curcur 的后缀链接都指向这个更“纯粹”的 cloneclone 状态。
    4. 最后，把 pp 的后缀链上，所有原本指向 toto 的转移边，全部重定向到 cloneclone（纠正历史遗留的指针）。

回到这道题目啊

1. 问题转化

题目要求我们找出 ss 的若干个子串，满足以下条件：

  1. 这些子串都不能包含 pp 作为子串。
  2. 任意两个选出的子串，互不为前缀（Prefix Code）。
  3. 选出的集合非空。
    如果不考虑包含 pp 的限制，所有子串的前缀关系天然构成了一棵前缀字典树（Prefix Trie）。题目中的“互不为前缀”，在树上等价于：选出的节点中，没有任何一个节点是另一个节点的祖先（即这组成了一个非空的反链 Anti-chain）。
    限制“不能包含 pp” 具有向下传递的性质：如果在字典树上某个节点对应的子串包含了 pp，那么它在字典树上的所有子孙节点（即所有以它为前缀的字符串）也必定包含 pp。因此，我们相当于在整棵前缀字典树上剪掉了一些子树，然后在剩余的有效树中选反链。

标红色的是因为包含了P，因此非法啊，如果按照这种前缀树的画法的话，那么起诉想表述的就非常清楚了

2. 树形 DP 计算反链数

在一棵普通的树上求反链的数量，可以通过树形 DP 解决。
设 dp[u]dp[u] 表示在以 uu 为根的子树中，选择反链的方案数加上1（加1代表在 uu 的子树中什么都不选的空集方案）。
• 如果我们不选 uu：可以在其各个子树中自由选择反链，根据乘法原理，方案数为 ∏v∈child(u)dp[v]\prod_{v \in child(u)} dp[v]。
• 如果我们选了 uu：那么 uu 的所有子孙都不能被选，方案数为 11。
两者相加，即：dp[u]=1+∏v∈child(u)dp[v]dp[u] = 1 + \prod_{v \in child(u)} dp[v]。
若在树中存在一条没有分叉的长为 LL 的链（即连续 LL 个节点都只有一个子节点），且链底部的子树 DP 值乘积为 DD，那么经过这 LL 个节点后，链顶部的 DP 值将恰好是 L+DL + D。

3. 利用后缀自动机 (SAM) 压缩字典树

由于 ss 的长度可达 5×1055 \times 10^5，前缀字典树的节点数可能是 O(∣s∣2)O(\vert{}s\vert{}^2) 的，直接建树会超时超空间。
这里有一个经典结论：字符串 ss 的前缀字典树，可以通过构建其反串 sRs^R 的后缀自动机 (SAM) 的 Link Tree (Parent Tree) 来完美压缩。
• 将 ss 反转得到 sRs^R，对 sRs^R 建立后缀自动机。
• sRs^R 的 SAM 的 Link Tree，其边代表在 sRs^R 串前添加字符，也就等价于在原串 ss 后面添加字符。
• 因此，Link Tree 中的每一个节点 uu，实际上代表了前缀字典树上的一条没有分叉的链。链上每个节点对应的子串，它们在原串 ss 中都有相同的起始位置 BuB_u。链上包含的字符串长度范围是 [len(link(u))+1,len(u)][len(link(u)) + 1, len(u)]。

4. KMP 结合 SAM 进行剪枝

我们需要知道 SAM 中每一个节点 uu 所代表的那条链，有多少个节点是“有效”的（即不包含 pp）。

  1. 在建立 SAM 时，记录每个节点在 sRs^R 中第一次出现的结束位置，以此可以推算出它在原串 ss 中的起始位置 BuB_u。
  2. 使用 KMP算法 找出 pp 在原串 ss 中的所有出现位置。然后预处理出数组 nxt[i]，表示在原串 ss 中，起点大于等于 ii 的最靠左的 pp 出现位置的终点索引。
  3. 对于 SAM 上的节点 uu，它的字符串起点为 BuB_u。
    ◦ 如果 pp 在 BuB_u 及其之后最早完整出现的地方，终点索引为 EE（即 E=nxt[Bu]E = nxt[B_u]），那么任何起点为 BuB_u 且长度 ≥E−Bu+1\ge E - B_u + 1 的字符串都会包含 pp。
    ◦ 意味着该链允许的最大有效长度为 Mu=E−BuM_u = E - B_u。如果 BuB_u 后面根本没有出现过 pp，则 Mu=∞M_u = \infty。
  4. 节点 uu 原本代表长度从 len(link(u))+1len(link(u)) + 1 到 len(u)len(u) 的链，剪去非法部分后，链上剩下的有效节点数量即为：Cu=max⁡(0,min⁡(len(u),Mu)−len(link(u)))\displaystyle C_u = \max(0, \min(len(u), M_u) - len(link(u)))

AC代码

心路历程（WA，TLE，MLE……）