字符串基础(1.0版本)

前言

几乎所有字符串算法都存在一个共性：基于所求信息的特殊性质与已经求出的信息，使用增量法与势能分析求得所有信息。这体现了动态规划思想。

Manacher 很好地证明了这一点：它维护所求得的最右回文子串的回文中心 $d$ 与回文半径 $r$，利用回文性质通过均摊右端点移动距离在线性时间内求出以每个位置为中心的最长回文半径。

SA，KMP，Z 与 SAM 等常见字符串算法无不遵循这一规律。读者在阅读时注意体会这种思想，笔者认为其对于提升解决问题的能力有很大帮助。

定义与记号

约定

• 文章使用打字机字体 texttt 描述一个字符串的具体内容，例如 s=stargames。
• 无歧义时，n 表示当前描述的字符串的长度。在字符串两侧加上 $|$ 表示长度。
• 当下标 i不在 [1,n]范围内时，对应位置的字符 si​ 视为空字符。

基本定义

• 字符集：字符集 可以是任何具有全序关系的集合 $\Sigma$，即 $\Sigma$ 中任意两个不同元素 $x,y\in \Sigma$（x≠y）可比较大小。除非特殊规定，一般按字母表顺序或数码大小比较元素。
• 字符：字符集 $\Sigma$ 中的元素称为 字符。sisi​ 或 $s[i]$ 表示 $s$ 的第 $i$ 个字符。
• 空串：不含任何字符的字符串称为 空串，记作 $ϵ$，$|ϵ|=0$。空串之于字符串类似空集之于集合。
• 子串：由 s在开头或末尾删去若干字符得到的字符串称为 s的 子串。s本身和空串均为 s的子串。s[l,r]或 sl, 表示 s 位置 l∼r上的字符连接而成的子串，当 l>r 时为空串。
• 反串：翻转 s 得到 s 的 反串，记作 s^R。
• 回文串：s=s^R的串称为 回文串。特别地，空串是回文串。
• 拼接：s+t表示将 t拼接在 s 后。

前后缀相关

匹配相关

• 出现位置：若 $s[p-|t|+1,p]=t$，则称 $t$ 在 $s$ 中以位置 $p$ 出现。$t$ 在 $s$ 中的 出现位置 等于 $t$ 的最后一个字符在 $s$ 中的对应位置。例如，若 $s=\text{abcbabc}$，$t=\text{abc}$，则 $t$ 在 $s$ 中的所有出现位置为 $\{3,7\}$。

• 匹配：称字 $t$ 匹配 $s$ 当且仅当 $t$ 在 $s$ 中出现。

• 模式串（单词）：用于匹配的字符串称为 模式串，相当于题目给定的 单词。

• 字典：题目给定的所有模式串的集合称为 字典。

• 文本串：被匹配的字符串称为 文本串。

• 分清模式串和文本串的定义：用 t匹配 $s$ 即求 $t$ 在 $s$ 中的所有出现位置，$t$ 是 用于匹配的串，称为模式串（模式串是我们要寻找的模式，是子串）；$s$ 是 被匹配的串，称为文本串（文本串相当于给出的文本，是主串）。

• 前缀：在 s末尾删去若干字符得到的字符串称为 s 的 前缀，形如 s[1,i]0≤i≤n），记作 prei。s本身和空串均为 s的前缀。
• 后缀：在 s开头删去若干字符得到的字符串称为 s 的 后缀，形如 s[i,n]（1≤i≤n+1），记作 sufi。s 本身和空串均为 s的后缀。
• 真前 / 后缀：真前缀 表示非原串前缀，真后缀 同理。
• 最长公共前缀：lcp(s,t)表示 s 和 t的 最长公共前缀（Longest Common Prefix），即最长的 u 使得 $u$ 同时为 $s$ 和 $t$ 的前缀。最长公共后缀（Longest Common Suffix）同理。
• 字典序：定义空字符小于任何字符。称 s 的 字典序 小于 t 当且仅当去掉 lcp(s,t)后，s的第一个字符小于 t 的第一个字符。等价于以第 i 个字符作为第 $i$ 关键字比较。