Qinshihuang's Blog

tmc的小窝

0%

字符串学习笔记

发表于 更新于

对不起了 zrz 字符串我忘光了

字符串哈希

万能的哈希，水过大量字符串题

DFA

确定有限状态自动机，是一类可以识别文本内容的自动机。

它由五部分组成：

  1. $\Sigma$，字符集。
  2. $Q$，所有的状态集合。
  3. $st$，一个特殊的状态 $st\in Q$ 表示起始状态。
  4. $F$，接受状态集合，$F\subseteq Q$。
  5. 状态转移函数 $\delta(q,c)$，从一个状态通过接收一个字符实现的转移。

如何识别字符串？一个 DFA 收到字符串后从 $st$ 出发按照转移函数一步步转移，如果最后状态 $q\in F$ 则此字符串可被接受，否则不可。

DFA 是理解很多字符串算法的基础。

例子：判定一个二进制串是否为偶数的 DFA：

在这个自动机中有两个状态 $Q=\{0,1\}$，字符集为 $\Sigma=\{\texttt{0},\texttt{1}\}$，初始状态 $st=0$，可接受状态集合 $F=\{0\}$，转移函数为

显然如果二进制的最后一位是 $0$，那么最终状态会停在 $0$ 上，即可被接受。

Trie 自动机

其实就是字典树啦

思想很好理解。每当插入一个新字符串，就从根节点向下转移，进一个字符 $c$ 就跳到 $\delta(q,c)$，如果没有这个节点就新建一个，最后在此次插入的终止节点上打上可被接受标记。

容易发现此结构形成了一棵树，而且其点数小于等于 $\sum|t_i|$，是一个经过空间压缩的存储字符串的结构。

一些应用

查询一个字符串是否在给定模式串里出现过

很简单，将给定模式串建出 Trie，遇到新的字符串就看能否被此 Trie 接受即可。

其总时间复杂度为 $\sum|s_i|+\sum|t_i|$。

查询一些正数中两两异或的最大值 P4551

经典的 01-Trie 应用。

考虑将每个整数从高位到低位写成二进制的形式（如果位数不同则补 $0$），容易贪心地发现两个数异或值想更大那么它们的高位要尽量不同。

将每一个二进制表示当成一个字符串来建出 Trie 来，此时直接把每一个数当成字符串在 Trie 上走即可，注意要走相反的字符而不是相同的字符。

总时间复杂度为 $O(n\log V)$。

AC 自动机

Trie 是 AC 自动机的结构基础。

KMP 自动机

KMP 自动机解决单模式串匹配的问题。

考虑一些暴力或者乱搞方式：

  • 哈希，先将模式串求出哈希值，再对文本串求子串哈希，然后枚举每个长度与模式串相同的子串看哈希值是否相等。时间复杂度为 $O(n+m)$，但是由于有大量取模运算常数较大，且有错误概率，一般并不常用。
  • 暴力，枚举每个起始点进行暴力匹配，跑得挺快，但是时间复杂度最大会被卡到 $O(nm)$，效率较低。
    • 随便一搞就可以搞出来，如 $s=\texttt{aaa…aaa}$，$t=\texttt{aaa…aaa}$，且 $|s|=2|t|$。

这样效率都不好。考察暴力做法，发现没有使用以前求出的信息，导致以前的计算被浪费了。这很不好。

Fail

考虑一个新的匹配方式，利用以前匹配成功的信息减少运算次数。

首先定义一个字符串 $s$ 的 border：$s$ 的一个非本身的子串 $t$，使得 $t$ 既是 $s$ 的前缀又是 $s$ 的后缀。

不妨设 $s$ 的一个 border 是 $t$，border 的性质有这么几条：

  1. $|t|$ 比 $|s|$ 至少少 $1$。
  2. $t$ 的 border 同样还是 $s$ 的 border。
  3. 一个字符串 $s$ 是重复字符串（即 $s$ 可以写成 $AAA\dots A$ 的形式）的充要条件是 $|t|\ge\dfrac{|s|}{2}$，且此时循环节的长度最大是 $|s|-|t|$。（这是为什么？）

性质 3 的证明：一张图结束疑问。

那得到 border 之后有什么用呢？

考虑我有两个字符串 $s_1,s_2$，如果当前我匹配到某一位时匹配失败了，我就不用再回到开头重新匹配，而是可以跳到当前成功匹配的最长 border 上继续匹配（因为两端是一样的）。

假设我已经求出了 $s_2$ 的每个前缀的 border，那么这个过程的时间复杂度是多少？

假设有一个指针 $p$ 指向当前 $s_2$ 匹配到的位置，考虑当 $s_1$ 向前匹配一位的时候，$p$ 最多加 $1$，而匹配失败时 $p$ 至少减 $1$，所以这个过程的时间复杂度是 $O(|s_1|+|s_2|)$，效率很好。

那么如何求出 border？

用相同的思路在 $s_2$ 上匹配自己一遍即可。时间复杂度为 $O(|s_2|)$。

这就是 KMP 自动机的核心思想，其中 border（或者更好听的名字：$\text{Fail}$ 指针）就是自动机的转移函数的一部分（另一部分当然是匹配成功的指针啦），而可接受状态只有一个就是 $s_2$ 的末端。

例子 P4824

首先不带删除的很简单对吧！直接 KMP 做即可。

考虑有删除怎么办，还是一样 KMP，在 KMP 的过程中将路过的字符以及其对应的 $\text{Fail}$ 压到栈中（方便还原状态），一旦遇到匹配成功的字符串就直接将这个成功的字符串从栈里面弹出去，并且根据栈顶还原匹配状态。

注意可能栈会被弹空了，这时候要还原状态为 $0$。

例子 P3426

线性的 KMP+dp 做法？没听说过，还是来个 $O(n\log n)$ 的暴力做法吧。

首先考虑一个印章合法的充要条件是什么？如果把印章字符串 $t$ 在欲印字符串 $s$ 上匹配，如果一次匹配的位置比上一次匹配的位置靠后超过 $|t|$ 个位置，那么就不可以。

其次，合法的印章一定是 $s$ 的 border。这个很显然吧。

然后一个暴力的做法呼之欲出：枚举每个 border 进行 KMP 匹配。

快速打完，交上去，诶，怎么有 80 分？

（注意到我说的不是“怎么只有 80 分”）

这样不优在哪里呢？一个关键是没有利用以前的信息。

考虑一个较短的 border，如果它能匹配一个较长的 border，那么较长的那个一定不优。

然后你从小到大去枚举 border，进行匹配即可。如果失败则替换答案。

可以证明这样的时间复杂度是 $O(n\log n)$。

AC 自动机

AC 自动机是上面两个玩意的综合。

考虑 KMP 的扩展，如果我有很多个模式串需要匹配，只使用 KMP 是不可行的（时间复杂度为 $O(n|s|+\sum|t_i|)$），需要一个更加高效的算法，而 AC 自动机就是这样一个东西。

AC 自动机的核心思想和 KMP 相同，即使用公共前缀后缀来进行信息利用从而节约时间。但不同的是：

  1. AC 自动机使用 Trie 树来存储大量的模式串。
  2. AC 自动机里的 $\text{Fail}$ 指针不一定指向当前的字符串，也可能指向别的字符串的某一位置。

所以这里构建 $\text{Fail}$ 就成了一个问题。

构建 $\text{Fail}$ 的基础方法

对于一个字典树上的点 $u$，假设比 $u$ 深度小的点的 $\text{Fail}$ 指针全部求出。考虑 $u$ 父亲节点 $f$ 的指针，它指向的是 $f$ 最长公共前后缀。注意到 $f$ 加上一个字符后变成 $u$，其后缀也同样增加一个字符，那么如果 $\text{Fail}_f$ 对应的节点有一个同样的字符转移，那么对应的节点就是 $\text{Fail}_u$。如果没有？继续跳。

这样可以跳 $\text{Fail}$ 来进行处理。

但是这样会被轻松卡掉，因为每次跳都要耗费大量时间，不划算。

Trie 图/AC 自动机完全体

考虑如何节省时间来跳 $\text{Fail}$，方式很神奇：让 Trie 从树变成图。

具体的，先前的 Trie 上每个节点只能从其父亲由一个字符转移而来。现在，我们让 Trie 上的每个节点的每个字符都有其对应的转移点。

那不存在对应字符转移的转移边意义是什么？是不断跳 $\text{Fail}$ 的最终结果。

比如说我有一个点 $u$，其并没有 $c$ 这个字符的转移。如果我必须转移 $c$ 这个字符，那么暴力的做法是不断地跳其 $\text{Fail}$ 指针直到找到有 $c$ 转移的那个节点 $v$。而现在我强制令 $\delta(u,c)=v$，这样不就能一步到位了吗？

那么如何构建 Trie 图呢？方法也很简单：广搜。

从根节点开始进行广搜，假设现在搜到了 $u$ 节点，接下来枚举字符集中的元素，假设枚举到 $c$。那么此时分两种情况：

  1. $\delta(u,c)$ 本来就存在，则记它为 $v$，那么就令 $\text{Fail}_v=\delta(\text{Fail}_u,c)$。这是为什么？为什么上面需要不断跳 $\text{Fail}$ 而这里不用？这就是 Trie 图的妙用，因为 Trie 图的一条边其实隐形地进行了多次跳 $\text{Fail}$ 操作，于是这里只需要跳一步即可。
  2. $\delta(u,c)$ 不存在，那么补充这条边，令 $\delta(u,c)=\delta(\text{Fail}_u,c)$。原理是完全相同的。

这样就将一棵 Trie 树变成了一个每个节点对每个字符都有一条转移边并且还有一个特殊的 $\text{Fail}$ 转移边的 AC 自动机，可以称之为 AC 自动机完全体了。

这个过程的时间复杂度显然为 $O(|\Sigma|n)$，$n$ 为 Trie 树上的点数并且小于等于 $\sum |s_i|$。

在线的查询

就是把一个字符串丢进去并且按照 AC 自动机的转移状态进行转移并且根据打标记的节点进行统计答案即可。时间复杂度？目测是 $O(n)$ 的，但实际上是——

为什么？考虑在 AC 自动机的匹配过程中有一步需要在匹配到一个成功节点后不断跳 $\text{Fail}$ 以找到更多可被匹配的节点。这个过程的时间复杂度是 $O(|t|)$ 的，而且可以被以下的数据卡掉：

1
2
3
4
5
6
7
8
aaa...abbb...bccc...cddd...d......
a
aa
aaa
...
aa...ab
aa...abb
......

这样子每个模式串都是一堆模式串的后缀，在匹配成功后会不断跳 $\text{Fail}$。时间复杂度是 $O(n^2)$ 的（至少是 $O(n\sqrt n)$ 吧，因为模式串的总和是给定的）。

离线的查询

这里用到一个东西叫做拓扑排序优化。

就是说，我在匹配到合法字符串时不往下跳了，直接在这上面打标记，最后在 $\text{Fail}$ 树上用拓扑排序的方式将答案收起来。

$\text{Fail}$ 树是啥？

顾名思义，就是 $\text{Fail}$ 指针形成的树。

为啥是树？很简单，$\text{Fail}$ 指针的高度一定降低，不会成环，因此为树。

这东西有的时候有大用处，因为它描述了不同字符串之间的公共前后缀关系。

例子 P3121

P3426 的加强，就是把一个字符串换成了多个。

完全一样的做法，就是换在了 AC 自动机上。

例子 P2414

一道很好的 $\text{Fail}$ 树题。

首先按照题目给的方式把 Trie 树建出来并建立 AC 自动机的 $\text{Fail}$ 指针。接着将 $\text{Fail}$ 指针抽离出来成为 $\text{Fail}$ 树。

如果 $x$ 号字符串在 $y$ 号字符串里出现在失配树上意味着什么？考虑从根节点到 $y$ 结尾路径上的点集合 $A$，如果 $x$ 是 $y$ 的子串，那么一定有一个元素 $s\in A$，使得 $\text{Fail}_u$ 指向的节点的一个前缀为 $x$。

这个原理很简单，$\text{Fail}$ 指向的是后缀，再有个前缀就是子串。

一个字符串的一个前缀是 $x$，那么这个字符串对应的节点一定在 Trie 上是 $x$ 的子树节点。

考虑将询问离线下来，并在失配树上跑出 dfn 序，再 dfs 整棵 Trie 树（这俩树千万别搞混了），对其路径上的点打标记，最后每到一个有查询的节点就查询对应被查询节点的子树内标记之和。这个过程可用树状数组进行维护。

总时间复杂度 $O(n\log n)$。

例子 P4052

首先正难则反，考虑求出不能被阅读的文本串数量。

即求出满足字符串内无法匹配到一些模式串的长度一定的字符串数量。看到匹配想到将模式串建立 AC 自动机。然后考虑 dp。

学长说 AC 自动机上的 dp 都十分套路。——某篇题解

说得好！考虑设 $dp_{i,q}$ 表示枚举到字符串的第 $i$ 位、且 AC 自动机上匹配到 $q$ 的可行方案数量。那么转移很简单。

为了方便，这里的转移方程采用贡献形式而不是统计形式，因为一般来说 AC 自动机的转移边不好统计。

假设现在从 $q$ 出发向下贡献。显然可以先枚举下一位字符 $c$ 是什么，并求出向下的状态 $q^\prime=\delta(q,c)$。考虑如果 $q^\prime\in F$，那么这个转移是不合法的（一旦转移就会出现可匹配的串），不可进行直接跳过，否则就累加上答案，$dp_{i,q}\rightarrow dp_{i+1,\delta(q,c)}$。

初始化是长度为 $0$、状态为空字符串时答案是 $1$，因为空字符串无法匹配任何一个字符串。

时间复杂度为 $O(|\Sigma|\cdot m\sum|s_i|)$。

例子 P3715

还是一样的的 dp，设 $dp_{i,q}$，意义一样，转移方程除了需要多次跳转指针以外完全一样（因为换成了字符串）。时空复杂度是 $O(L\sum|s_i|)$。

但是你发现这玩意爆了。考虑优化。

设 $l=\max\{s_i\}$，考虑当固定 $i>l$ 时是什么情况。显然在转移的时候枚举每个状态，将此状态的前面转移到这里。显然此状态是否为结尾状态是已知的。

因此这个转移方程可以写成状态转移到状态的一个方程。

这东西是个矩阵啊。

利用矩阵转移加速，时间复杂度为 $O\left(\left(\sum |s_i|\right)^3\log L\right)$，就能过了。

upd：实现细节好多啊！！！

一个没有注意到但是致命的问题

在一个大结构体里经常会使用重载 = 来方便编写程序。但是这会出现问题，因为在结构体内的 = 运算一定不要有返回类型，一定要是 void！

比如，以下这段代码就会 RE：

1
2
3
4
5
6
7
8
struct matrix {
   int n,a[105][105];
   matrix operator =(matrix A) {
       n=A.n;
       for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
           a[i][j]=A.a[i][j];
   }
}

而这段代码就没事：

1
2
3
4
5
6
7
8
struct matrix {
   int n,a[105][105];
   void operator =(matrix A) {		//换成了 void
       n=A.n;
       for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
           a[i][j]=A.a[i][j];
   }
}

例子 P2603

初看这道题：什么鬼东西这东西真的可做吗？

再看一下，似乎是类似于匹配的问题，但是这个匹配函数也太牛马了吧。

考虑判定两个点列是否可以匹配。

实际上，一个点列在平面内就是一条折线，其中相邻的每两条线段之间都有两个关键值：夹角 $\theta$ 与比值 $p$。显然如果两个长度相同为 $n$ 的点列，从第二条线段开始，第 $i$ 与第 $i-1$ 条线段的夹角与长度比值均相同，那么可以肯定，这两个点列可以匹配成功。

注意这里的角是有方向的。

接下来，发现 $(\theta,p)$ 就可以完成一个转移了。所以把这个鬼东西看成转移边，将欲匹配的点列建成 AC 自动机（一定记得要将原点列与翻转后的点列一起丢进去），并且将母串求进去进行匹配即可。

难点其实在于求线段比值与线段夹角。其实也不难，线段比值可以直接将其平方后记录比值的最简分数，夹角则可以用内外积进行比较。都可以转化成整数与整数进行比较，就没有精度丢失的风险了。

没写，周六再调试吧。这东西肯定一写3个小时没了