字符串学习笔记

Black_Porridge · 2022-12-05 22:54:09 · 个人记录

感觉不开坑就永远想不起来要写。趁着现在能想起来先占个坑/mgx

说句闲话，感觉大家都好卷啊。为什么算法学习笔记都能写那么多字。

Hash

一些概念

• 哈希的定义：是字符串的一种映射，通过这种映射，我们可以判断两个字符串是否相同。

• 哈希函数的运用：

  字符串 s 的哈希函数 f(s)=\sum_ {i=1}^{|s|} s_i \times base ^{|s|-i} \% mod，其中 base 和 mod 均为自己选择。一般情况下我们选择大质数作为 mod，这样 f(s) 的分布是比较均匀的，哈希表的查询复杂度也可以近似为 O(1)（具体的会在后文提到）。

  对于比较两个字符串是否相等，只需要判断它们的哈希函数是否相等即可。具体的，对于一个字符串 s 的子串 s_{l,r}=\{s_l,...,s_r\}，它的哈希函数 f(s_{l,r})=\sum_ {i=l}^{r} s_i \times base ^{r-i} \% mod =(f(s_{1, r}) - f(s_{1, l-1}) \times base^{r-l+1}+mod) \% mod。即可在 O(1) 时间内进行字符串的比较。

• 哈希冲突

  当发生两个不同的字符串哈希值相同时，我们称此时发生哈希冲突。一般解决哈希冲突会使用哈希表。而哈希表分为开散列法和闭散列法两种写法。开散列法是在每一个位置拉一个链表，将哈希值相同的字符串存放其中；闭散列法是每当发生哈希冲突时，将字符串的哈希值对应为原哈希值后的第一个没有对应字符串的哈希值。一般我们使用开散列法，而它每次操作的复杂度为 O(\dfrac{n}{mod})，当 mod 为大质数时，可以认为它是 O(1) 的。

练习题

• Acwing137. 雪花雪花雪花 哈希表/最小表示法

  注意常数。

• AcWing 138. 兔子与兔子

  直接比较哈希值

• AcWing 139. 回文子串的最大长度 Manacher/二分+哈希

  预处理字符串的哈希值前缀和 hash1 /后缀和 hash2。枚举回文子串的中心 i，之后二分以 i 为中心的最长回文子串长度 len。若 len 为奇数，检查 (hash2_{i-len/2}-hash2_{i} \times base^{len/2}+mod)\% mod 与 (hash1_{i+len/2}-hash1_{i} \times base^{len/2}+mod)\% mod 是否相等。若 len 为偶数，检查 (hash2_{i-len/2+1}-hash2_{i+1} \times base^{len/2}+mod)\% mod 与 (hash1_{i+len/2}-hash1_{i} \times base^{len/2}+mod)\% mod 是否相等。

kmp