字符串，就是由字符连接而成的序列。

常见的字符串问题包括字符串匹配问题、子串相关问题、前缀/后缀相关问题、回文串相关问题、子序列相关问题等。

(K)MP

作用：在文本串s中快速查找模式串p的所有位置。

本质：π(i) = s{0…x-1} == s{i-x+1…i} 中最大的x

$pmt[i]:$ 从$p[0]$往后数、同时从$p[i]$往前数相同的位数，在保证前后缀相同的情况下，最多能数多少位。

$next[i]:$ 储存可以匹配上的文本串$s$的位置。

其实并不用掌握真正的KMP就够用了。

板子

KMP自动机

KMP 自动机就是一个不断读入待匹配串，每次匹配时走到接受状态的 DFA。

EXKMP

作用：$O(n)$求出一个字符串的所有后缀与一个字符串的的最长公共前缀的长度。

本质：Z(i) = s{0…x-1} == s{i…i+x-1} 中最大的x

具体讲解

板子

$ext[i]:$ 表示文本串的子串$s[i,x−1]$与$p$的最长公共前缀的长度。

$z[i]:$ 表示模板串的子串$p[i,x−1]$与$p$的最长公共前缀的长度。

Manacher

作用：与回文子串有关

本质：d(i): 以s[i]为中心的奇回文子串的数量。

类似EXKMP。

板子

SA

本质：sa[i]：将所有后缀排序后第 i 小的后缀的编号

rk[i]：表示后缀 i 的排名，是重要的辅助数组，（sa[rk[i]] == rk[sa[i]] == i）

板子

Trie

本质：接受且仅接受指定的字符串集合中的元素。

可持久化（类似主席树）

它是最简单的$DFA$

可持久化板子

AC自动机

本质：接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串，也就是 Trie + KMP。

可持久化

板子

SAM

本质：接受且仅接受指定字符串的后缀。

直观上，字符串的 SAM 可以理解为给定字符串的 所有子串 的压缩形式。值得注意的事实是，SAM 将所有的这些信息以高度压缩的形式储存。

一个 SAM 最多有 $2n-1$ 个节点和 $3n-4$ 条转移边。

板子

后缀通用设计思路

后缀数组维护这个图叶子的排名和其它附加值。

后缀自动机表示的所有状态。

广义SAM

本质：接受且仅接受指定的字符串集合中的某个元素的后缀，也就是 Trie + SAM。

板子