另一种阅读体验


字符串哈希

Trie 树

在计算机科学中,trie 树,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。

与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。

一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。

一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

在 Trie 上,两个字符串的最长公共前缀(LCP)就是两个点的最近公共祖先(LCA)所对应的点。

有些时候,我们也可以将数字看作一个二进制数,或者输一个由 $0/1$ 组成的定长字符串,来解决一些问题。

KMP 算法

KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

前置知识

border 指所有那些既是前缀又是后缀,但不是本身的子串。

border 的 border 仍是 border。

一个串的所有 border 互为 border。

若 Lborder 为一个串的最长 border,那么一个串的 Lborder,Lborder 的 Lborder $…$ 为这个串的所有 border。

所以实际上每个前缀都指向自己的 Lborder(没有则指向超级根),可以形成一个树形结构,每个点到根的路径就是所有 border。

$T-c$ 是 $S-c$ 的 border($c$ 是一个字符),那么 $T$ 是 $S$ 的 border。(反过来不一定成立)

换句话说,$S-c$ 的 Lborder 一定是 $S$ 的一个 border 增加一个字符得到的。(注意这里没有 $L$)

怎么对 S 的每个前缀求 Lborder?

假设我们求出了 $S$ 的所有前缀的 Lborder,那么按照刚刚的性质从长到短暴力枚举 $S$ 的所有 border $T$,找到第一个使得 $T$ 后面字符是 $c$ 的即可。

方便起见,记 $S[1][r]$ 表示 $S$ 从第 $1$ 个字符到第 $r$ 个字符形成的子串。

首先 $S[1][1]$ 的 Lborder 是 $0$。

从 $i=2$ 到 $i=n$,假设已经求出了 $S[1][1],…,S[1][(i-1)]$ 的 Lborder,现在要求 $S[1][i]$ 的 Lborder,根据刚才的讨论,只要枚举 $S[1][(i-1)]$ 的 border 即可,即令 $j=Lborder[i-1]$,然后不停的令 $j=Lborder[j]$,直到 $j=0$ 或者 $S[j+1]==S[i]$ 为止。

显然 $Lborder[i]\le Lborder[i-1]+1$,而每一轮 $j$ 跳跃次数不超过 $|Lborder[i]-Lborder[i-1]|$,由于总有 $Lborder[i]\ge 0$,所以 Lborder 变小的幅度之和不会超过变大的幅度之和,而变大的幅度之和显然是 $\text{O}(n)$ 的,因此复杂度线性。

每个 border 都与一个不严格循环节一一对应。

也就是说,如果 $m$ 是长为 $n$ 的字符串 $S$ 的一个 border,那么 $m-n$ 就是 $S$ 的一个不严格循环节,反之亦然。

因此找到一个串的所有不严格循环节,只要枚举一个串的所有 border 即可。而(严格的)循环节就是那些使得 $(m-n)|n$ 的长为 $m$ 的 border。

AC 自动机

考虑一个 KMP 的 EX 版本。

给定一个模板串 $T$,和若干匹配串 $S_1…S_m$,对每个 $S_i$ 询问其在 $T$ 中出现几次。

$|T|\le 100000,Si$ 总长 $\le 100000$

考虑把 $S$ 放到一块建类似 $nxt$ 一样的东西(在 AC 自动机中叫 fail 指针)。

先将 $S$ 建 Trie,考虑在 Trie 上运行 $T$。

当遇到无法匹配的情况时,希望找到 $T$ 已匹配部分的一个最长后缀,使得这个后缀也是某个 $S$ 的前缀。

注意这里实际上和 $T$ 无关,我们只需要对 Trie 上每个节点对应的字符串做这件事情即可。

换句话说,我们要对每个点找到其最长后缀也是某个 $S$ 的前缀,而 $S$ 的前缀必然对应 Trie 上一个点,或者说我们需要找到一个失配节点(fail)。

具体的找法用一个 BFS 就能实现。

除了一些特殊情况,一个点的 fail,就是其 failfail 的对应子节点(如果有的话),没有的话就继续跳 fail

可以证明这样做的复杂度是正确的。

匹配 $T$ 的时候,就用 $T$ 在 $S$ 上面跑,每次失配就沿着 fail 指针向上跳直到可以继续匹配为止。

这样复杂度显然是线性的。

注意问题

一个点对应的字符串出现的次数需要统计子树和,比如 abcd 的对应节点出现一次,那么 bcd,cd,d 都要出现一次。

直接如此实现会有常数上的劣势,一个显著的改进方法是:若该点有 $c$ 的出边,一个点的 $ch[c]$ 等于其对应的儿子;否则这个点的 $ch[c]=$ 发生失配时最终转移到的点。

只需要在求 fail 的时候,对于第二种情况(假设当前是 $x$)$ch[x][c]=ch[fail[fa[x]]][c]$ 即可,注意特判根节点周围的一圈点。

这样能显著优化常数,而且在做另一些问题时能简化问题。

给 n 个串然后两两询问的题有些时候的处理方法

考虑选一个适当大小的数字 $s$,那么一个串长度要么不超过 $s$,而长度超过 $s$ 的只有不超过 $\dfrac ms$ 个。

若询问两个长度均不超过 $s$ 的串,那么直接 KMP 即可,复杂度 $\text{O}(s)$;

若询问中有至少一个串长度超过 $s$,假设是 $A$,那么用 AC 自动机预处理所有串在 A 中出现了几次,复杂度是 $\text{O}(m)$ 的,由于这部分 $A$ 只有不超过 $\dfrac ms$,所以这部分预处理复杂度 $\text{O}(\dfrac{m^2}s)$。

因此总复杂度 $\text{O}(qs+\dfrac{m^2}s)$。

取 $s=\sqrt{\dfrac{m^2}q}$ 时有最小值 $O(\dfrac m{\sqrt{q}})$。

不过大多数题 $m,q$ 同阶,所以偷懒取 $s=\sqrt{m}$ 也行。

具体取多少还可以适当调参来加速。(因为两部分算法有常数差异)

后缀数组 SA

SA 能在 $O(n\log n)$ 的时间内将所有后缀按照字典序排序,然后求排名相邻的两个后缀的 LCP(最长公共前缀),结果是排序后的结果。

一个简单的推论是,两个后缀的 LCP 就是后缀数组对应位次间所有相邻字符串 LCP 的最小值,这样可以 RMQ(区间最值查询)。

可以利用 SA 求一个字符串有多少本质不同的子串(即长的不一样),或者求一个字符串的第 $k$ 小等。

这些问题本质相同:

考虑如何按从小到大的顺序得到 $s$ 的所有子串。

由于子串就是后缀的前缀,所有我们只需要考察所有后缀的前缀即可。

从小到大考虑 $SA$ 中的后缀,假设考虑到了第 $i$ 个和第 $i-1$ 小的后缀的 LCP 是 $L$,那么第 $i$ 小的后缀的长小于等于 $L$ 的前缀都是已经考虑过的,而长大于 $L$ 的前缀都是新出现且字典序逐渐增大的子串。

那么这两个问题解决了。

第二个问题通过二分可以 $O(\log n)$ 回答。

同理也可以求一个子串的位次,方法是先找到所在后缀,对应到 SA 上,考虑二分出一个最小的以这个子串为前缀的后缀(即两个后缀的 LCP 长度大于等于子串长度),然后求一下现在这个后缀和前一个后缀的 LCP 即可算出该子串的位次。

因此可以用 SA 实现子串和位次的转化。

同时参照上面的方法也可以求出一个子串在哪些位置出现过。

后缀树

后缀树是一种数据结构,是前缀树里的一个特殊类型,能快速解决很多关于字符串的问题。

一个 string S 的后缀树是一个边被标记为字符串的树。

因此每一个 $S$ 的后缀都唯一对应一条从根节点到叶节点的路径,这样就形成了一个 $S$ 的后缀的基数树。

SAM(后缀自动机)

SAM 就是将 DFA 与后缀结合,将重复的后缀压缩成只有一个,这样省下了空间。

后缀自动机厉害的地方就在于空间时间都是线性复杂度的,十分优秀。

SAM 的每个状态 $st$ 都包含了一部分 $S$ 的子串,记作 substrings(st),并且对于两个不同状态 $u$ 和 $v$,包含的子串 $substrings(u) ∩ substrings(v) = ∅$;

每个子串都恰好被一个状态包含,所以我们只要构造出来 $S$ 对应的 SAM,再对所有状态 st 求 $Σ(maxlen(st)-minlen(st))$ 就是子串的数目。

SA-IS

SA−IS 排序是基于诱导排序这种思想,将问题规模缩小,解决更小的问题,快速解决原问题的算法。

Manacher 算法

Manacher 算法,又叫 “马拉车” 算法,可以在时间复杂度为 $\text{O}(n)$ 的情况下求解一个字符串的最长回文子串长度的问题。

在进行 Manacher 算法时,字符串都会进行一个字符处理,比如输入的字符为 acbbcbds,用 “#” 字符处理之后的新字符串就是 #a#c#b#b#c#b#d#s#。

回文自动机

同其他自动机一样,回文自动机是个 DAG(有向无环图),它用相当少($\text{O}(n)$)的空间复杂度存储了这个字符串所有回文串的信息。

和别的自动机不太一样,回文自动机是有两棵树的森林:其中一棵是长度为偶数的回文串集合,另一棵是长度为奇数的回文串集合,这两棵树的根节点分别表示长度为 $0$(空串)和 $-1$(无实际含义,便于运算)的回文串。

一个回文自动机包含不超过 $|S|$ 个节点,每个节点都表示了这个字符串的一个不重复的回文子串,同时一个节点会有不超过字符集大小的边连向其他节点,以及一条 fail 边连向这个点的 fail $…$

自动机中每条有向边都有一个字符类型的权值,起点的串左右分别加上这个字符得到的就是终点的串。

举个例子:设一条边权为 $c$ 的边连接的两个点分别是 $A,B$,$A$表示回文串 aba,则 B 表示的回文串就是 cabac。

特别的,如果 $A$ 是那个长度为 $−1$ 的根,$B$ 串就是这条边的权值。

当你插入一个字符的时候,插入的点代表的就是这个字符匹配的最长回文串,也就是说从根节点往下顺着边走,记着一个 str 一开始为空,一边走一边不停地往 str 左右两边添加新的字符,走到一个点,这个点代表的回文串就是 str

每个点都有个 fail 边,这条边指向这个点所代表的回文串的最长回文后缀所在的那个点(最长回文后缀:串中满足回文的最长的后缀,这个串自己不算)。

如果没有,则指向 $0$(就是那个根节点)。

特别的,$0$ 的 fail 节点就是那个长度为 $-1$ 的点。

分类: 文章

Audrey_Hall

I am trying to bribe you with uncertainty, with danger, with defeat.

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。

*

code