C20250021's blog
7.31 串串课堂内容
C20250021 LV 10 @ 2024-7-31 19:45:01

7.31 串串

1. kmp part

思想是对于每一位求出最长的后缀等于前缀的长度 $\operatorname{next}$

最短的周期就是串长减去 $\operatorname{next}$ ，

所有周期长度都是最小周期的倍数：

$a$ 和 $b$ 是周期，则 $\gcd(a,b)$ 为周期。

弱周期引理： $|S|$ 的两个周期 $a,b$ ，如果 $a+b\le|S|$ ，有 $(a,b)$ 也为 $|S|$ 的一个周期。

周期引理： $|S|$ 的两个周期 $a,b$ ，如果 $a+b-(a,b)\le|S|$ ，有 $(a,b)$ 也为 $|S|$ 的一个周期。这样我们证明了如果串不是最小周期的倍数，则这个串没有循环节。

这个是叫做周期引理，可以见上面记录周期与 $\operatorname{border}$ 的一些理解了。

P2375 [NOI2014] 动物园

求 $\operatorname{next}$ 数组，使得 $\operatorname{next}$ 数组的前缀后缀不重叠。

输出 $\prod\limits_{i=1}^n(num_i+1) \bmod 10^9+7$ 。

板子

[ARC077F] SS

给定一个偶串 $10^5$ （定义为两个相同字符串拼接而成的串），定义操作 $f(s)$ 为在 $s$ 后加入最少的字符（至少一个）使其变成一个新的偶串， $s$ 唯一确定 $f(s)$ ，问 $f^{10^{100}} (s)$ 的 $l,r\le10^{18}$ 位每个字符出现了多少次。

如果最小周期是一个循环，那么可以发现会一直重复这个循环。

$A(B)->AB(A)->ABA(AB)->ABAAB(ABA)$

说明： $ABA$ 的最小循环节是 $A$ 反证导矛盾

2.AC自动机

$\operatorname{fail}$ 指针的意义：一个点的 $\operatorname{fail}$ 指针的意思是指向了从跟到这个点最长的一节后缀的位置，因为每个点的 fail 指针是唯一的，所以我们可以建出来一个 $\operatorname{fail}$ 树。

主串遍历：保留最长一个后缀进行匹配，能匹配上的 $\operatorname{fail}$ 树上所有祖先。

注意，不补全的写法：就是跳 $\operatorname{fail}$ 进行匹配

通常是存不下边集（字符集很大） $\operatorname{map}$ 映射这样的写法。

例题

P2414 阿狸的打字机

CF163E e-Government

CF547E Mike and Friends

CF587F Duff is Mad

给定 $n$ 个字符串 $s_{1 \dots n}$ 。
$q$ 次询问 $s_{l \dots r}$ 在 $s_k$ 中出现了多少次。
$n,q,\sum_{i=1}^n |s_i| \le 10^5$ 。

两种角度：枚举文本串，枚举模式串

（文本：主串，模式：用来匹配的串）

若串长度 $>sqrt$ 我们尝试对该串离线，顺序枚举前缀串的 $\operatorname{fail}$ 树链

若串长度 $<sqrt$ 我们对前缀串离线，枚举当前串到根。

3. manacher

本质上在继承的过程。

加入间隔字符使得回文中心总是落在中间

回文优先想 $\operatorname{manacher}$ 过程，因为方便。

本质上势能，但是有奇怪的题需要分析更为抽象的势能。

例题

P5446 [THUPC2018] 绿绿和串串

逆转函数

注意到来回映射

贡献为 $m$

映射类似于 $\operatorname{manacher}$

尝试 $\operatorname{manacher}$ 继承，考虑怎么算子区间贡献？

单个中心继承的时候维护所有前缀

主席树（卡空间）/可以直接移动吗？

4.EX kmp(Z函数)

用 $O(n)$ 的时间求得每个后缀与串开头的 $\operatorname{lcp}$ 长度。

记忆方式：与 $\operatorname{manacher}$ 相同，尝试继承。

ARC058F

$5s，n\le2000$ 个串，选择一些串，使得按照给出顺序拼接起来长度恰好为 $k$ ，字典序最小， $k\le10^4，\sum s=10^6。$

倒着做 $01$ 背包，然后现在是优先保证字典序

顺序 $\operatorname{dp}$ ，出来的串是唯一的。

然后 $\operatorname{exkmp}$ 可以直接比较字典序做到 $\operatorname{O(nk)}$ 。

P5334 [JSOI2019] 节日庆典

给定串 $S$ ，你需要对于每个前缀串 $T$ 求出来其最小字典序循环移位串 $(S_{i\sim t} + S_{1\sim i−1} )$ ，多个 $\operatorname{id}$ 保留最小的一个。

5.Trie

字典树，从上往下插入，一般处理插入与排序的字符串问题。（ $\operatorname{dfs}$ 嘛）

常见： $0/1\ trie$ ，从高位往低位贪心。

P5283 [十二省联考 2019] 异或粽子

给定长度为 $n\le10^5$ 的序列，然后定义一个区间的权值为区间的 $a_i\ \operatorname{xor}$ 在一起，问：所有区间 $\dfrac{n(n-1)}{2}$ 个中，权值前 $k\le 10^5(ex 10^9)$ 大的和是多少？

显然想法是一个一个数，经典的对于每个右端点数其左端点，然后做多

路归并：每个 $r$ 有 $l$ 的区间 $[x,y]$ 然后找到最大划分开，复杂度 $nlog$ 。

P6623 [省选联考 2020 A 卷] 树

给定一棵 $n$ 个结点的有根树 $T$ ，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$ 。

设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\dots,c_k$ ，定义 $x$ 的价值为：

$ val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x)) $

其中 $d(x,y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数， $d(x, x) = 0$ 。 $\oplus$ 表示异或运算。

请你求出 $\sum\limits_{i=1}^n val(i)$ 的结果。

建立可以整体 $+1$ 的 $\operatorname{trie}$ ：从低往高位建树。

[ABC240Ex] Sequence of Substrings

$2.5\times10^4$ 的字符串，问最多从里面选出来多少个不相交的子串，使他们字典序是最长上升子序列，字符串只由 $\operatorname{0/1}$ 组成。

只会用到 sqrt，做上升子序列，trie 比较子串。

SA

$\operatorname{rk}$ 数组： $\operatorname{id -> rk}$

$\operatorname{sa}$ 数组： $\operatorname{rk -> id}$

height 数组：排序后 $i$ 和 $i-1$ 的 l $\operatorname{cp}$ 是多少

求解方式：按照 $\operatorname{id}$ 枚举求解，$\operatorname{height\ rk\ i \ge height\ rk\ i-1\ -1}$

对于两串之间的 $\operatorname{lcp}$ 就是 $\operatorname{min height}$ （说明：相邻三个）。

本质上： $\operatorname{lcp}$ 好求

例题

P2178 [NOI2015] 品酒大会

P1117 [NOI2016] 优秀的拆分

给定一个串有多少子串使得对于当前子串存在 $\operatorname{AA}$ 的表示方式

串长 $3\times10^5$

关键点法：本质上是在考虑匹配 $\operatorname{AA}$ 的过程，你注意到形如如果 $mid$ 往右边移动，那么这个 $end$ 会移动两格，不好处理。

想法：确定匹配串长，枚举 $\operatorname{A}$ 的串长是多少，比如枚举串长为 $k$ 。

每 $k$ 个放置关键点，一定跨越。

一个小 $\operatorname{trick height}$ 分组。

并查集合并，维护最大次大，最小次小。

BZOJ4453 cys 就是要拿英魂！

给定一个字符串，给定一个区间，

问：区间中字典序最大的一个后缀。

串长 $10^5$

直观的想法：倒着扫描线嘛（动 $l$ 不动 $r$ ），有你一个角度是直接取 $rk$

最大的，但是会有截断。

维护当前从右向左单调栈，形如 $rk$ 减， $id$ 减。

如何求得目前限制下最优的一个？想要尽量靠近栈底，且是连续包含关

系的最靠栈顶的一个，维护相邻 $lcp$ 和 $r$ 的关系，二分。

END.

7.31 串串课堂内容

7.31 串串