嘿嘿嘿……字符串……我的串串……

都别催！！！等我有时间了例题和详细讲解都会补回来的！！！

一些约定

在此博客中，为更方便的表示字符串的相关信息，我们使用如下记法：

• 字符集：一般记作 \(\Sigma\)，是一个包含可能的所有输入字符的、建立了全序关系的集合，具体视题目而定。一般是一个泛性的概念。\(\Sigma\) 中的元素称为 字符。

  全序关系：\(\Sigma\) 中的任意两个不同的元素 \(\alpha\) 和 \(\beta\) 都可以比较大小，要么 \(\alpha<\beta\)，要么 \(\beta<\alpha\)。

• 字符串：由 \(n\) 个字符顺次排列形成的序列，\(n\) 称为 \(S\) 的长度，表示为 \(|S|\)。

• 字符 与 子串：对于一个字符串 \(S\)，本文中，我们使用 \(S[i-1]\) 或 \(S_{i-1}\) 表示其第 \(i\) 个字符，即 下标从零开始，这点务必注意。使用 \(S[i\dots j]\) 来代表顺次排列的 \(S[i],\dots,S[j]\) 形成的字符串，即 \(S\) 从 \(i-1\) 到 \(j-1\) 个字符形成的子串。。

8.5 - 基础字符串算法

哈希

哈希函数

考虑实现一个哈希函数 \(h: S \to \mathbf{Z}\)，其中 \(S\) 指一个字符串，把输入字符串映射到一个较小、方便比较的值域中。这个哈希函数一般是 \(h(S) = ( \sum_{i=0}^{ |S|-1} S_i \cdot a^i ) \bmod p\)，其中 \(a\) 是一个自定的、应 \(\geq |S|\) 的任意整数。

哈希冲突

一个经典的例子是 生日冲击问题。

生日问题 / 生日悖论：如果想让一群人中至少有两个人生日相同，根据鸽巢原理，我们需要 367 个人；但如果是想让至少两个人生日相同的概率达到 \(99.9%\)，只需要 \(70\) 个人；而如果概率是 \(50%\)，那么只需要 \(23\) 个人就够了。

生日冲击问题告诉我们，函数对随机数据映射产生冲突的概率是指数级增长的。对于一个值域是 \([1,m]\) 的函数，\(\sqrt{m}\) 个数就可以让映射冲突的概率大于 \(\dfrac{1}{2}\)，对于哈希函数也同理。

双哈希 / 多哈希

于是，我们可以考虑构造多个哈希函数，比如选取不同的模数 \(p\)。这样，我们可以大概认为，两个字符是相同的，当且仅当他们的所有哈希函数都对应相同。

在具体做题中，通过预处理所有前缀 / 后缀的 hash 值得到 \(O(1)\) 计算所有子串的方法，从而 \(O(1)\) 判断子串是否相等，是一种常见的应用。

字典树 - Trie

这个词念 [triː]，或者 [traɪ]。

最小表示法

给出一个字符串，求与它循环同构的串中字典序最小的串。

\(O(n)\) 的做法是，比较两个由 \(i,j\) 开头的子串，如果第一个不同的地方是 \(S[i+k],S[j+k]\)，且 \(S[i+k]>S[j+k]\)，那么 \(S[i\dots i+k]\) 不可能称为最小表示的开头。所以从头到尾扫一遍就可以了，维护一个开头在哪里。

Manacher

马拉车嘿嘿……

用于统计所有回文子串数量，考虑通过枚举回文中心，寻找当前回文中心的最大回文子串来统计。

维护一个已找到的 \(r\) 最大的回文子串\([l,r]\)，如果当前枚举的回文中心 \(i>r\)，则暴力向两边尝试扩展，找到最大的回文子串；否则，\(i\) 关于维护的回文子串 \([l,r]\) 的回文中心对称的点 \(j\)（即 \(l+(r-i)\)），\(i\) 的最长回文子串长度至少和 \(j\) 的回文子串在 \([l,r]\) 以内的部分长度相等，从这部分开始尝试向外暴力扩展即可。

时间复杂度 \(O(n)\)。

KMP

前缀函数与 KMP，非常有趣的知识，后期会详细介绍。