字符串全家桶（持续更新）

· · 个人记录

现已加入KFC豪华套餐

<从零开始的字符串学习指南>

本文综合了@adolphshi所有学过的字符串算法，会一直不定期更新。
但是这个人太懒了，什么时候弃坑了也不一定

0 <前言、统计与目录>

0.1 <统计>

开坑日期2023-11-2
hash 完成日期 unknown
tire 树完成日期 unknown
KMP 完成日期 2023-11-30

0.2 <前言>

最近看了很多的字符串算法，于是就想写一篇博客记录下来。也希望这篇博客可以帮助一部分人。
也是为了不被卡在需要对字符串进行处理的题上.
这里的字符串算法有极大概率没有代码,代码和例题可能完结以后再进行添加.
这里默认 S 为一个字符串， S_i 为 S 的第 i 个字符， S_{i,j} 为 S 的 i ~j 的子串，n 为字符串 S 的长 度。

在此处,若无提前声明,默认字符串的长度是从 1 开始的.

0.3 <目录>

\large{\text{1.hash }} \large{\text{2.tire树 }} \large{\text{3.KMP }} \large{\text{4.AC自动机 }} {\text{待续\dots}}

1 < hash >

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围——OI wiki

hash(哈希) 其实一点也不难理解,通俗来讲,就是将一个字符串压缩成一个 k 进制(通常为 31 或 113)的数字,然后可以做到 O(1) 进行比较(或进行存储).当然,若是直接压缩成一个 k 进制数字,通常会爆long long,因此我们可以对一个大质数 p 取模(当然也可以自然溢出).

但是若对数字取模后,数字会重复(即有两个不同的字符串对应的数字相同),这种情况被称为哈希冲突.处理哈希冲突的方法有二:

因为我们将字符串看成了一个 k 进制再模 p 的整数,所以我们可以使用类似前缀和的思想来进行快速的求出子串的哈希值.

![图片here]()

2 <tire树>

字典树，英文名 trie。顾名思义，就是一个像字典一样的树。——OI wiki

tire 树是字符串算法中非常重要的一个算法,因为后面的自动机都需要用到 tire 树.

2.1 普通tire树

话不多说，先放图

ps：也是oi-wiki的图

其中根节点到各个节点的路径代表一个字符串,节点之间的连边代表一个字符,但是不难发现，若是下面两组数据　　

aa 
aba
ba
caaa
cab
cba
cc
aa 
aba
ba
caaa
cab
cba
cc
c

便会发现两组数据建出来的树相同.此时我们只需将每一个字符串的末尾打上标记即可. 加粗即为末尾标记.

其中tire树最为常见的操作是查找字符串(不然叫什么字典树啊),方法也很简单,就是顺着路径向下找就行了,若找到的最后一个点有末尾标记,便可以找到.

2.2 <01 tire>

顾名思义,就是只有01两个分支的tire树.用01tire树可以很方便地求最大异或值,维护异或和等操作.

2.2.1 <01 tire 维护最大异或和>

其实不难,因为最大异或和就是希望找一个数字与另外一个数字使其尽可能不同,到 01 tire 上就是尽可能地向另外一条边走即可.

在此时的01 tire上可以再进行其他的修改操作,这里就不再赘述,感兴趣的读者自行探索.

2.2.2 <01 tire 当平衡树>

拿 01 tire 当普通平衡树是最好不过的了,它码量小,易于理解.

实现就是将每一个数字转成二进制再由高位到低位放入 01 tire 中,tire 的 每一个节点都再维护一个子树大小即可.它基本可以完成普通平衡树所做的所有内容,就是所需空间大小有点大.

2.3 <可持久化 tire 树>

没什么好讲的,就是每将一个 tire 树更新是再进行路径复制即可,代码(按理来说)与主席树没有什么区别.

3 < KMP >

因此 Knuth–Morris–Pratt 算法（简称 KMP 算法）用 O(n + m) 的时间以及 O(n) 的内存解决了在字符串中查找子串的问题.——OI wiki

KMP 算法是一个快速匹配子串与母串的算法,它的核心思想就在于利用字符串的重复减少在匹配时的向后跳跃(比较难表述,学完就知道了).

3.1 <前缀函数>

前缀函数(在OI中常用为 next 数组)是一个记录前缀后缀相同的最长的字符串的个数的函数.

前缀函数是 KMP 的一个非常重要的前置芝士,因为 KMP 的核心就在于利用前缀函数减小时间复杂度.

前缀函数如图:

此处的橙色箭头所指的位置的前缀函数的值为2,因为蓝色部分与红色部分的字符串是相同的,也是最长的字符串.

但是正常情况下,用暴力的方法去求单个字符的前缀函数是 O(n) 的,不过我们可以利用前缀函数的一些性质来做到 O(n) 递推地预处理出字符串每一个字符的前缀函数.

在 KMP 中用到的 next 数组,一般都是不包含自身的最长相同前后缀,且通常为相同的长度 +1 ,因此我们在接下来的预处理 next 数组的时候也按照此规则进行.

我们规定空字符串的最长相同前后缀为0.
递推过程可以用下面一幅图来讲： 我们要进行处理绿色的地方的 next 数组的值,我们比对两个黄色指针所指的地方,若两个黄色指针所指的字母相同,则先同时加一,再将第一个黄色下表当做绿色位置的 next 数组的值.
若不同,则第一个黄色指针跳回上图中蓝色位置(是那个数的 next 值)再进行下一轮比对.
这里的正确性请读者自证.

在预处理出 next 数组后,接下来就是进行 KMP 了.

3.2 <KMP 算法>

在 KMP 算法之前,请各位读者回想一下朴素的字符串匹配:
两个下标字符相同时同时加一,不同时一个回到子串开头,一个回到母串开始匹配的位置加一，再继续进行下一轮匹配。

而 KMP 算法的思想就是让母串的下标不向回退,这样就可以做到 O(n) 匹配字符串了.但是这样子串的下标肯定是不能再向前调回刚开始的位置了,显然正确性是没有保障的. 这时候回想一下我们的 next 数组(其实也不用回忆了,刚看完), next 数组处理的是最长相同的前后缀因此我们直接跳至该位置的 next 数组指向的下标即可.

还是以这张图为例,当我们在倒数第二个字符处失配时,可以发现,他前面的九个字符与开头的九个字符完全相同,那么这九个字符就不需要进行匹配了(因为匹配到这一个字符时除了这一个字符,前面的字符都应该相等,那么就是后缀与前缀相同的部分就无需再进行匹配了),这样就保证了正确率.

3.3 <KMP 算法的可视化>

这是一个附加的内容,因为我认为我的KMP讲的不太好(本来是有动图的,但是存动图的图床寄了QAQ),很难让读者理解(包括复习时的我),特此,在下面添加一个可以亲自操作的 KMP 可视化的网站:
link
这个可视化的网站与我所讲的还是有一些出入,原因包括但不限于下标问题,一开始可能会对一部分人造成一定的误解,请谅解.

4 <AC自动机>

AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的自动机，用于解决多模式匹配等任务。——OIwiki

简称 AC自动机=tire+KMP (doge)

AC自动机的作用上文也说了,其实就是快速进行多个子串在母串中的匹配.AC自动机能将原为O(n^2)的多子串匹配将至 O(n) (可能有点常数,其中母串与子串同阶).

当然,这个AC自动机并不能使你封号,但我这里还有一个可以让你封号的自动AC机.
脖子右拧(不是我的博客,也不能在洛谷用)

好了,话不多说,接下来开始AC自动机的学习:

4.1 <失配指针>

失配指针是需要将所有要进行匹配的字符串放进一个tire树中,然后再加上类似next数组的指针. 回想一下,我们在之前KMP中学到的next数组的定义: 最长相同前后缀的长度(位置) 而失配树的定义与其类似,但是是所有字符串中与当前字符串的后缀相同的最长前缀.这么说可能有点难以理解,下面放一个图:

图中为 aa aba ba c 的tire树.其中从5号节点与7号节点指出的fail边为5号节点与7号节点的失配指针.容易发现,该节点所代表的字符串的后缀与所指节点的前缀相同.

对于一颗tire树上的所有失配指针(没有可以匹配的失配指针指向根节点),把它们构成的树称之为失配树,该tire树的完整失配树如下:

因为加上原来的边会使这颗树看着十分混乱,因此我把他删去了,所以建议与上图一起看.

那如何构建一颗这样的树呢?

其过程也与next数组的构建过程类似: bfs进行构建. 先找到该节点的 father 再跳至 fail[father] 处,看有没有向相同方向的边,如果有,那么将 fail[now] 指向当前位置并结束, 如果没有将指针跳至 fail[fail[father]] 处继续判定.直到到达根节点,此时将 fail[now] 指向根结点.

下面放一组图方便理解:

我们此时求7号节点的fail指针(0~6号节点的fail指针已经求出,但是无关紧要的我未画出)
我们找到7号节点的父亲节点: 5号节点,发现它业有一条a的边,那么就将7号节点的fail指针连向6号节点.

若是上面这张图片,发现2号节点并没有a边,于是继续顺着2号节点的fail指针向上,找到根节点,发现根节点有一条a边,便将7的fail指针连向1.

那么我们的失配树就构建完了,接下来就是在失配树上跑KMP就行了.

我们通常在构建tire树时,就只是构建一颗树.但是,在AC自动机中,我们还需要记录这个节点在向后加一个字符串后的fail边,并且将这条fail边直接当成字典树的边.

例如上图中的点4,点4下面是没有节点的,但是当我们找到它,而它下一个是b时,我们假想一个节点x,让它的fail边为4号节点的一条出边.如下:

4.2 <AC自动机>

AC自动机的原理很简单,其实就是将KMP的过程移到了tire树上而已,不过还是有一些区别的,所以我讲一下.

顺着tire树(图,因为我们多加了一部分边)向下找,若失配,顺着fail指针向上回退,若找到末尾标记,则这个位置的ans +1.
在所有的字符串都找完后,顺着fail树自底向上累加ans即可得到每一个的匹配次数.

这边借用一张OIwiki的图辅助理解: