跳转至

基本概念

本文主要记录一些基本的字符串概念和子串结构相关的东西。

算是字符串全家桶的引论吧，主要参考了策爷的讲稿1。

Definitionsψ(｀∇´)ψ

本文使用 1-Index。

  • 字符串：一系列字符构成的有序可重集，一般使用 \(s,t\) 来表示。
    • 一般使用 \(|s|\) 来表示一个字符串的长度。
  • 字符集 \(\Sigma\)：字符串中的所有字符都应当属于这个集合，一般取 \(|\Sigma| = 26\) 即 \(26\) 个小写英文字母。
  • 子串：记 \(s[l..r]\) 表示 \(s\) 中第 \(l\) 个字符到第 \(r\) 个字符构成的一个串，即 \(s[i]s[i + 1]s[i + 2]\dots s[r - 1]s[r]\)。
  • 前缀：记 \(pre(s, x) = s[1..x]\)，称作 \(s\) 的一个前缀。
  • 后缀：记 \(suf(s, x) = s[n - x + 1, n]\)，称作 \(s\) 的一个后缀。
  • 字典序：若 \(\exists i \text{ s.t. } s[i] < t[i]\)，且 \(i\) 为最小的使得 \(s[i] \not= t[i]\) 的 \(i\)，那么称 \(s < t\)。

Period and Borderψ(｀∇´)ψ

  • Period：如果 \(\exists p \in (0, |s|] \text{ s.t. },\forall i \in [1, |s| - p],s[i] = s[i + p]\)，则称 \(p\) 为 \(s\) 的一个 Period。
    • 说人话，Period 是 \(s\) 中不重叠地重复出现的一个子串的长度（最后一段可能不完全出现）。
  • Border：如果 \(\exists x \in [0, |s|) \text{ s.t. }, pre(s, x) = suf(s, x)\)，则称 \(pre(s, x)\) 为 \(s\) 的一个 Border。
    • 注意 \(x\) 不能等于 \(|s|\)，换句话说 Border 是一个真前缀，满足对应长度的真前缀和真后缀相等。
    • LBorder：最长的 Border。
  • 前缀函数 \(\pi\)：\(\pi(i) = \max\{j\}, (s[1\dots j] = s[i - j + 1 \dots i], j < i)\)。
    • 换句话说 \(\pi(i)\) 表示 \(pre(s,x)\) 的 LBorder 长度。
  • KMP 算法：在 \(O(n)\) 的时间内快速求出 \(\pi(i), i \in [1,n]\)，传送门。

LCP and Heightψ(｀∇´)ψ

  • LCP(Longest Common Prefix)：最长公共前缀，也就是 \(x \text{ s.t. }, pre(s, x) = pre(t, x)\)，记为 \(lcp(s,t)\)。
  • Suffix Array：对 \(s\) 的所有后缀排序，得到的第 \(i\) 小的后缀 \(suf(s, x)\) 的编号 \(x\)，有 \(O(n \log n)\) 的倍增求法和 \(O(n)\) 的线性求法，传送门
    • Hit: 排序是按照字典序排序的。
  • Height：\(h[i] = lcp(sa[i], sa[i - 1])\)，也就是第 \(i\) 名的后缀和它前一名的后缀的 LCP，\(h[1] = 0\)。
    • 可以利用一个引理线性求 \(h[i], i \in [1,n]\)，这个在下面会提到。
  • Z func：\(z(i) = lcp(s, suf(s, i))\)，也就是 \(s\) 和它长度为 \(i\) 的后缀的最长公共前缀。
    • 存在一个类似 KMP 的线性算法(EXKMP)可以快速求出 \(z(i), i \in [1,n]\)，传送门

Automationψ(｀∇´)ψ

OI 中常用的自动机为 DFA（Determined Finite Automation）即确定有限状态自动机。

其包含五个部分2：

  1. 字符集（\(\Sigma\)），该自动机只能输入这些字符。
  2. 状态集合（\(Q\)）。如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。
  3. 起始状态（\(st\)），\(st\in Q\)，是一个特殊的状态。
  4. 接受状态集合（\(F\)），\(F\subseteq Q\)，是一组特殊的状态。
  5. 转移函数（\(\delta\)），\(\delta\) 是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个 DFA 看成一张有向图，那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。

DFA 的作用就是识别字符串，一个自动机 \(A\)，若它能识别（接受）字符串 \(S\)，那么 \(A(S)=\mathrm{True}\)，否则 \(A(S)=\mathrm{False}\)。

当一个 DFA 读入一个字符串时，从初始状态起按照转移函数一个一个字符地转移。如果读入完一个字符串的所有字符后位于一个接受状态，那么我们称这个 DFA 接受 这个字符串，反之我们称这个 DFA 不接受 这个字符串。

如果一个状态 \(v\) 没有字符 \(c\) 的转移，那么我们令 \(\delta(v,c)=\mathrm{null}\)，而 \(\mathrm{null}\) 只能转移到 \(\mathrm{null}\)，且 \(\mathrm{null}\) 不属于接受状态集合。无法转移到任何一个接受状态的状态都可以视作 \(\mathrm{null}\)，或者说，\(\mathrm{null}\) 代指所有无法转移到任何一个接受状态的状态。

我们扩展定义转移函数 \(\delta\)，令其第二个参数可以接收一个字符串：\(\delta(v,s)=\delta(\delta(v,s[1]),s[2..|s|])\)，扩展后的转移函数就可以表示从一个状态起接收一个字符串后转移到的状态。那么，\(A(s)=[\delta(st,s)\in F]\)。

自动机常常用来做字符串匹配的问题，所以介绍几个基本概念：

  • 模式串 \(s\)：匹配的字符串。
  • 文本串 \(t\)：被匹配的字符串。

这么说可能有点抽象，我们举个例子。

现在给定你一个串 \(s\)，要问 \(s\) 在 \(t\) 里的哪些位置出现过，此时的 \(s\) 就是模式串，\(t\) 就是文本串。

一些常用的自动机：

  • Trie: 只接受给定的模式串集合中的元素的自动机。
    • 我们把字符串插入 Trie 的时候打上的 end 标记，实际上就是说明了这个状态所代表的字符串是被自动机所接受的。
    • 在这里，我们定义一个状态 \(u\) 所代表的字符串是 \(st \to u\) 这条路径上所有转移边的字符按顺序构成的字符串。
  • KMP 自动机：只接受以给定的模式串 \(s\) 为后缀的自动机。
    • 状态转移函数 \(\delta(u, ch)\) 为：
    • \(\delta(u, ch) = \begin{cases}\text{NULL} &s[1] \not= ch\land u = 0\\ u + 1 &s[u + 1]=ch\\ \delta(\pi(u), ch) &s[u + 1] \not= ch \land u > 0\end{cases}\)
    • 我们也可以称 \(\pi\) 为 KMP 自动机的“失配指针”，意义为当“下一个”状态不是接受状态的时候，状态转移函数去向的状态。
  • AC 自动机：只接受一些字符串 \(s\)，满足对于给定的模式串集合 \(S\)，\(\exists p \in S \text{ s.t. } \exists x \text{ s.t. } p = suf(s, x)\)。
    • 所以也有很多人认为 AC 自动机是 Trie + KMP，不过我感觉这个定义不够严谨。
  • 后缀自动机：只接受给定模式串 \(s\) 的后缀的自动机。
    • SAM 是接受模式串 \(s\) 的最小 DFA，这个性质很重要。
    • 通常被用来解决子串相关的问题。
  • 广义后缀自动机：把 SAM 放到了 Trie 上，能接受多个模式串的。
    • AC 自动机可以近似的看作广义 KMP 自动机，这与广义 SAM 和 SAM 的关系是类似的。

有两个很重要的东西，大部分的字符串匹配都和这个相关：

  • 后缀链接：字符串匹配的一个重要思想是，如果这个串不行，我们就试试它的后缀行不行。所以大部分的自动机中都有后缀链接的思想，在 AC 自动机上体现为 Fail 指针，在 KMP 自动机上体现为 Next 指针。

  • 后缀链接树：自动机的后缀链接通常会形成一棵树，比如 AC 自动机和 KMP 自动机的 Fail 树。它们通常因为自动机本身的性质，会拥有一些美妙的性质，并以父子关系，路径，LCA 等等图论概念的形式呈现。

Theories and Lemmasψ(｀∇´)ψ

因为时间关系暂时不给出证明，读者可以自行查找。

之后会陆续补上。

  • Weak Periodicity Lemma：若 \(p, q\) 是字符串 \(s\) 的周期，且 \(p + q \le |s|\)，那么 \(\gcd(p, q)\) 也是 \(s\) 的周期。
  • Periodicity Lemma：若 \(p, q\) 是字符串 \(s\) 的周期，且 \(p + q - \gcd(p, q) \le |s|\)，则 \(\gcd(p, q)\) 也是 \(s\) 的周期。
  • 等差数列引理：若字符串 \(s,t\) 满足 \(2|s| \ge |v|\)，则 \(s\) 在 \(t\) 中的所有匹配位置形成等差数列。

  • Border 结构：

    • 字符串 \(s\) 的所有不小于 \(\dfrac{|s|}{2}\) 的 Border 长度构成一个等差数列。
    • 字符串 \(s\) 的所有 Border 长度排序后可以分成 \(O(\log |s|)\) 段，每段是一个等差数列。

  • Height 引理：\(h[rk[i]] \ge h[rk[i - 1]] - 1\)，其中 \(rk\) 是后缀的排名。

  1. 《字符串算法选讲》- 金策 ↩

  2. 引用自 OI-wiki - 自动机 ↩

最后更新: July 16, 2023