1. 子串 (substring) 是指字符串中连续 `k ge 0` 个字符组成的串.
  2. 子序列 (subsequence) 是指字符串中 `k ge 0` 个字符按原次序组成的串, 不要求连续.
  3. 切片 (slice) 与 python 一致, 我们用 s[i:j] 表示左闭右开区间 s[i] ... s[j-1]. 特别当 i == j 时, 表示一个空串. 可以省略左边界或右边界, 比如 s[i:] 表示一个后缀, s[:j] 表示一个前缀. 当一个前缀/后缀的长度严格小于 `s` 的长度时, 称它为 `s` 的真前缀/真后缀.

模式匹配

[来自 OI Wiki]

前缀函数

前缀函数 (prefix function) 设字符串 `s` 的长度为 `n`. 如果子串 `s[:i+1]` 有一个真前缀等于真后缀, 则称它们是 `s` 在下标 `i` 处的一个匹配对 (或 border). `s` 的前缀函数定义为一个长度为 `n` 的数组 `pi`, 其中 `pi[i]` 表示 `i` 处的最长匹配对的长度: `pi[i] := max_(0 le k le i) { k: s[0:k] = s[i-k+1:i+1] }`. 当我们顺序读取字符串 `s` 的时候, 前缀函数告诉我们, 最近读取到的几个字符如何与 `s` 的开头进行匹配.

由定义知 `pi[0] = 0`.

接下来, 我们寻找计算前缀函数 `pi` 的递推算法. 已知 `pi[i]`, 如何求 `pi[i+1]` 呢? 最好的情况是 `s[i+1] = s[pi[i]]`, 这时我们直接扩展 `i` 处的最长匹配对, 就得到 `i+1` 处的最长匹配对:

扩展性质 相邻的前缀函数值最多增加 1: `pi[i+1] - pi[i] le 1`, 等号成立当且仅当 `s[i+1] = s[pi[i]]`.

    记 `pi[i] = a`, `pi[i+1] = b`.
  1. 去掉 `s[i+1] = s[b-1]` 这一对相等字符就得到 `s[:i+1]` 的一个匹配对, 故 `pi[i] ge b-1`.
  2. `rArr`: 若 `b - a = 1`, 则有 `s[i+1] = s[b-1] = s[a]`.
  3. `lArr`: 若 `s[i+1] = s[a]`, 则 `pi[i+1] ge a+1`, 即 `b - a ge 1`, 但已知 `b - a le 1`, 所以 `b - a = 1`.

如果不巧 `s[i+1] != s[pi[i]]`, 则 `i+1` 处的最长匹配对不能由 `i` 处的最长匹配对扩展而来. 但它可能由 `i` 处的其它匹配对扩展而来. 因此我们由长到短枚举 `i` 处的所有匹配对, 判断它能否扩展为 `i+1` 处的匹配对. 如果它们全都无法扩展, 且 `s[i+1] != s[0]`, 则 `pi[i+1] = 0`.
因此, 关键问题是如何枚举 `i` 处所有匹配对. 下面的性质告诉我们, `i` 处的每个匹配对的长度可以由前面计算过的 `pi` 值得到.

可以归纳证明 `pi[i] le i`.

    次长匹配对性质 设 `i` 处有两个匹配对, 长度分别为 `j, k`: `s[0:j] = s[i-j+1:i+1]`,
    `s[0:k] = s[i-k+1:i+1]`.     假设 `j lt k`, 那么上式推出 `s[0:j] = s[k-j:k]`. 得到 `k-1` 处的一个匹配对. 我们证明以下两个命题等价:
  1. `j` 恰好是 `k-1` 处的最长匹配对长度, 即 `j = pi[k-1]`.
  2. `j` 是 `i` 处仅次于 `k` 的匹配对长度.

`j` 不是 `i` 处仅次于 `k` 的匹配对长度
`iff` 存在 `j lt m lt k`, 使得 `s[0:m] = s[i-m+1:i+1]`
`iff` 存在 `j lt m lt k`, 使得 `s[0:m] = s[k-m:k]`
`iff` `j` 不是 `k-1` 处的最长匹配对长度.

计算前缀函数 这是一个在线算法, 意思是可以逐个读取 `s` 的字符进行处理, 不必保存整个串.
设 `s` 的长度为 `n`, 则空间复杂度为 `O(n)`. 如果已知 `pi` 的最大值 `max pi = m`, 则只需存储 `pi[0:m]`, 就可满足迭代步骤 j = pi[j-1], 空间复杂度降低到 `O(m)`.
为了得到时间复杂度, 从迭代步骤 j = pi[j-1] 入手. 由于 `pi[j-1] le j-1`, 每迭代一次 `j` 的值都至少减小 1. 但 `j` 的值非负, 所以 `j` 减小的次数不超过 j = j+1 的执行次数, 即不超过 `n`. 因此时间复杂度为 `O(n)`.

字符串的周期 由前缀函数的定义, 字符串 `s` 的最长匹配对长度是 `pi[n-1]`, `n` 是 `s` 的长度. 那么 `n - pi[n-1]` 就是 `s` 的最小周期. 比如 abcabcabc 的最长匹配对长度等于 6, 最小周期 = 9-6 = 3.

KMP 算法

该算法由 Knuth, Morris, Pratt 在 1977 年提出, 其核心就是前缀函数的应用.

KMP 算法 在字符串 `s` 中查找子串 `p` 出现的所有位置. 记 `s, p` 的长度分别为 `m, n`. 为此构造一个字符串 `p \# s`. 其中 `\#` 表示一个不出现在 `p` 和 `s` 中的分隔符. 计算新字符串的前缀函数, 若 `pi[i] = n`, 由定义知道存在一个右端点在 `i` 的子串与待查找的字符串 `p` 相等. 扣除 `p` 与分隔符的长度, 这个子串在 `s` 中的下标为 `i - (n-1) - (n+1) = i - 2n`.
KMP 算法的时间复杂度为 `O(m+n)`. 由于分隔符的存在, 前缀函数值不超过 `n`, 所以空间复杂度为 `O(n)`.

自动机

    自动机 (automation) 是一张有向图, 其中
  1. 每个节点表示一个状态, 每条边上带有一个指令, 表示状态转移的条件.
  2. 存在一个特殊节点, 称为起始状态. 图中的每个节点都可以从起始状态到达.
  3. 自动机从起始状态开始, 每次读取一个指令, 然后根据指令跳转到下一个状态. 我们把这个过程编码为一个状态转移函数, 其中 `"state"_1, "state"_2` 是转移前后的状态, `"actions"` 是输入的指令序列. 例如字符串可以看作指令序列, 每个字符都是一个指令. `delta("state"_1, "actions") to "state"_2`.
  4. 当所有指令处理完毕, 根据自动机最后的状态可以作出一些判断, 比如字符串是否匹配等. 通常把表示匹配成功的状态称为接受状态.
    5. (自动机与动态规划的区别??)

序列自动机

后缀自动机 (SAM)