字符串算法笔记

记号约定：

• \(|s|\)：字符串 \(s\) 的长度。
• \(\mathbb{S}\)：字符串集。
• \(\Sigma\)：字符集。

一些约定：

• 下标从 \(0\) 开始。

1. 哈希

1.1 定义

我们想要快速求出字符串 \(s\) 是否等于 \(t\)。

如果 \(|s| \neq |t|\)，那么一定不相等，所以令 \(|s| = |t| = n\)。那么有 \(O(n)\) 的暴力。

我们肯定想要更优的的算法。我们发现，计算机求出两个数是否相等只需要 \(O(1)\)，那么只需要想办法把 \(s\) 变成一个数就行了。具体的，我们想求出 \(H : \mathbb{S} \to \Z\)，满足 \(\forall s \neq t, H(s) \neq H(t)\)。

考虑进制数，于是可以定义：

\[H(s) = \sum_{i = 0}^{|s| - 1} B^i s_i \]

其中 \(B\) 是常数。这样需要 \(O(n)\) 预处理，但可以 \(O(1)\) 查询。

这个想法只能停留在理论，因为计算机存不下太大的数。那我们退一步，给 \(H\) 取个模：

\[H(s) \equiv \sum_{i = 0}^{|s| - 1} B^i s_i \pmod M \]

但是这样会破坏 \(H\) 原有的性质，一定 \(\exists s \neq t, H(s) = H(t)\)。这样的情况被称为哈希冲突，我们肯定希望这样的情况尽量减少。

通过选定足够好的 \(B\) 和 \(M\)，可以让 \(H\) 在数据随机时几乎不冲突，但是面对专门的 hack 数据时则会心有余而力不足。但是，我们可以发动人类智慧来降低冲突概率。

实现时一般令 \(M = 2^{64}\)，这样就不用取模，直接用 unsigned long long 存就可以了。OI Wiki 使用了 \(B = 233\)，但其实只要 \(B > \max(\Sigma)\) 就可以了。

1.2 改进

1.2.1 多模哈希

既然哈希一遍会出问题，那我们就多哈希几遍。我们选定多组 \((B_i, M_i)\)，从而产出多个哈希函数 \(H_i\)。

对于两个字符串 \(s, t\)，当且仅当 \(\forall i, H_i(s) = H_i(t)\) 时才判定它们相等。

实现时，一般做两遍哈希。这样既节省时间，还增加了正确率。

1.2.2 \(O(1)\) 查询字串哈希

给定字符串 \(s\)，求 \(s\) 的子串 \(s_l s_{l + 1} \cdots s_r\) 的哈希。

我们使用前缀和的思想，令 \(H_i\) 为 \(s_0 s_1 \cdots s_i\) 的哈希，则有递推式：

\[H_i \equiv H_{i - 1} + B^i s_i \pmod M \]

那么可以 \(O(n)\) 预处理。

如何查询？如果直接 \(H_r - H_{l - 1}\)，那肯定不对。但比较接近了，分析一下：

\[H_r - H_{l - 1} = \sum_{i = l}^r B^i s_i = B^l \sum_{i = l}^r B^{i - l} s_i = B^l \sum_{i = 0}^{r - l + 1} B^i s_{i + l} \]

发现这离正确答案只差 \(B^l\)，所以正确答案就是 \(\dfrac{H_r - H_{l - 1}}{B^l}\)。

实现的时候可以顺便预处理一下 \(B\) 和 \(B\) 的逆元的次幂。查询是 \(O(1)\) 的。

1.3 应用

1.3.1 多次询问 LCP 的长度

注：LCP（Longest Common Prefix）指最长公共前缀。

我们想求字符串 \(s\) 和 \(t\) 的 LCP。设 \(\min(|s|, |t|) = n\)，很明显有 \(O(n)\) 的暴力。

如何优化？注意到 LCP 具有单调性，那么可以二分答案，但是 check 是 \(O(n)\) 的。我们一通优化让时间复杂度变劣了。

我们发现，check 就是求出 \(s\) 的前缀和 \(t\) 的前缀是否相等，这可以用哈希优化。于是时间复杂度变成了 \(O(\log n)\)。