Hash

计算哈希

$\text{Hash}(S)=(\sum_{i=1}^{|S|}{S[i]\cdot b^{|S|-i}})\bmod m$ 先预处理出 $b$ 的幂，递推出 $S$ 的所有前缀的 hash 值，然后就可以 $O(1)$ 得到 $S$ 任意字串的 hash 值。

哈希冲突

生日悖论

根据不严谨的计算，当 $mod$ 与 $n^2$ 同阶，hash 冲突概率约为 50%

双 Hash

对 $S$ 用两个不同的模数取模，两个 hash 值都相等才认为字符串相等，通常可以令 $S$ 的最终 hash 值为两个 hash 值的乘积。 相较于自然溢出，双 hash 常数较大 听说有人想在 Codeforces 用自然溢出

哈希应用

判定字符串相同

hash 值相等即为相同

字符串比大小

每次把字符串分别劈成两半，如果前一半 hash 值相同就继续比较后一半 hash 值，否则继续比较前一半 hash 值，直到串长为 1，hash 值大的显然更大

求 $lcp$ (longest common prefix)

显然可以二分

回文子串

把字符串 $S$ 正着 hash 一遍，倒着 hash 一遍，枚举回文中心，二分回文半径即可

乱搞

字符串题不会做可以考虑 hash 乱搞，通常题目也会给 hash 设置部分分

暴力优化系列

Manacher

用途

对每个位置 $i∈|S|$，求出 $a[i$] 表示 $s[i−a[i]+1…i+a[i]−1]$ 为一段极长的回文子串。

算法

1. 由于回文中心可能在两个字符之间，所以对原串 $S$ 进行预处理，在两个字符之间插入特殊字符，特别地，头尾要另外添加各不相同的另外两种特殊字符以避免边界问题
2. 枚举 $1\ldots|S|$，过程中维护历史 $i+a[i]$ 的最大值 $b$ 以及取到该最大值的下标 $p$
3. 对于每次枚举，求解 $a[i]$ 方式如下:
   1. \begin{cases}

a[i]=1& (otherwise)\ \end{cases}$$

2. 暴力更新 $a[i]$
3. 维护 $b,p$

复杂度分析

显然复杂度瓶颈是第 2 步的暴力更新次数，在第 1 步之后，若 $a[i]$ 取 $a[p∗2−i]$，那么说明此时的 $a[i]$ 已经是正确的了，不可能再变大，第 2 步的循环不会执行，否则 a[i] 取 $b−i$ 或 $1$，则 $b\leq i+a[i]$，则第 2 步中每执行一次循环 $a[i]+i$ 均变大 1，再在第 3 步中更新到 $b$，执行了多少轮循环，$b$ 就增加多少，而 $b$ 最大为 $|S|$，因此第 2 步的循环在整个算法中只会执行 $O(|S|)$ 次。

Z Function

用途

对 $S$ 的每个位置 $i∈|S|$，求出 $z[i]$ 表示 $S[i\ldots i+z[i]-1]$ 是极大的 $S$ 的前缀，即 $lcp$。 对 $T$ 的每个位置 $i∈|T|$，求出 $d[i]$ 表示 $T[i\ldots i+z[d]-1]$ 是极大的 $S$ 的前缀。

算法

1. 枚举 $2\ldots|S|$，过程中维护历史 $i+z[i]$ 的最大值 $b$ 以及取到该最大值的下标 $p$
2. 对于每次枚举，求解 $z[i]$ 方式如下:
   1. \begin{cases}

z[i]=0& (otherwise)\ \end{cases}$$

2. 暴力更新 $z[i]$
3. 维护 $b,p$
4. 特别地，根据定义不同，$z[1]=|S|$ 或 $0$
5. 求解 $d$ 的方式同理，且下标从 1 开始枚举

复杂度分析

同理:[[!字符串总结#Manacher#复杂度分析]]

DFA 系列

DFA （确定有限状态自动机）

DFA 构成

1. 状态集 $Q$
2. 可接受状态集 $q_A$
3. 初始状态 $q_0$
4. 字符集 $C$
5. 转移函数 $\delta(q,c)$

如何自动

一开始，状态位于起始状态 $q_0$，接下来，将待判断的串的每个字符依次输入 每输入一个字符 $c$，就将当前状态从 $q$ 移动至 $δ(q,c)$。 若将给定串的所有字符输入完毕后，最终所在的状态状态 $q_{end}∈q_A$，则输入的串是可接受串。

Trie

$Q=树节点$ $q_A=字符串结尾字母所在节点$ $q_0=0\,号节点$ $C={depends}$ $\delta(q,c)=q\,代表的字符串后面加上字符\,c\,代表的字符串所在节点$

KMP

对于字符串 $T$,设 $right_T$ 为 $T$ 相等前后缀的长度的集合 观察到“在 $T$ 后输入什么样的字符串才能让 $T$ 变为可接受字符串只与 $right_T$ 有关 设 $q=right_T$ 观察到只要确定 $q$ 中最大元素就可以确定整个 $q$，于是 设 $q^{'}=\max \{ \ x|x\in q \ \}$
设 $fail[q^{'}]=\max ⁡\{\ x|x\in q \quad \&\& \quad x<q^{'}\ \}$ $Q=\{ \ q \ |\ q^{'}\in \ 1,2,3\ldots,|S| \}$ $q_A=\{ \ q \ |\ q^{'}\ = |S| \}$ $q_0=\{ \ q \ |\ q^{'}\ = 0 \}$ $C=depends$ 有转移

$$fail[q^{'}]=\begin{cases} 0&(q^{'}=1)\\ \delta(fail[q^{'}-1],c)&(otherwise) \\ \end{cases}$$$$\delta(q^{'},c) \begin{cases} q^{'}+1&(q^{'}<|S| \quad \& \& \quad S[q^{'}+1]=c ) \\ 0& (q^{'}=0 \quad \& \& \quad S[q^{'}+1]\neq c)\\ \delta (fail[q^{'}],c)&(otherwise) \\ \end{cases}$$

ACAM（Aho_corasick Automaton）

与 KMP 类似地,设 $H=\{可能成为某个模式串的前缀的字符串的集合\}$ 设 $q=right_T=\{\ |S|\ |\ S\ 是\ T\ 的后缀\ 且 \ S\in H\}$ 设 $q^{'}=\{ \ \ S\ |\ \quad |S|=\max (|S|\in q)\ \}$
设 $fail[q^{'}]=⁡\{\ q\ 中第二长的字符串\}$ $Q=\{ \ q \ |\ q^{'}\in S \ 的前缀 \}$ $q_A=\{ \ q \ |\ q^{'}\ = S \}$ $q_0=\{ \ q \ |\ q^{'}\ = \emptyset \}$ $C=depends$ 有转移

$$fail[q^{'}]=\begin{cases} \emptyset &(|q^{'}|=1)\\ \delta(fail[fa[q^{'}]],c)&(otherwise) \\ \end{cases}$$$$\delta(q^{'},c) \begin{cases} q^{'}+c&(q^{'}<|S| \quad \& \& \quad q^{'}+c\in H) \\ \emptyset & (q^{'}=\emptyset \quad \& \& \quad c\notin H)\\ \delta (fail[q^{'}],c)&(otherwise) \\ \end{cases}$$

Summary from

《信息学竞赛中的字符串问题选讲》浙江省余姚中学 诸一行