字符串哈希

字符串哈希是一种将任意长度的字符串映射成一个非负整数的算法。

将字符串视为 PP 进制数，对于字符集 [1]^{[1]} 中的每一个字符，分配一个正整数。一般情况下，分配的数值都远小于 PP，PP 一般可以取 131131 或 1333113331。因为这个数可能很大，我们需要将这个数对 MM 取模。在实践中，可以使用 unsigned long long 类型存储哈希值，在计算过程中不处理算数溢出问题。unsigned long long 在溢出时会自动对 2642^{64} 取模。

  • 可加性：记字符串 SS 的哈希值为 H(S)\text{H}(S)，在字符串 SS 后增加一个字符 cc，则 H(S+c)=(H(S)×P+V(c)) mod m\text{H}(S+c)=(\text{H}(S) \times P+\text{V}(c)) \bmod m，其中 V(c)\text{V}(c) 代表给字符 cc 赋予的值。
  • 可减性：记字符串 S+TS+T 的哈希值为 H(S+T)\text{H}(S+T)，在字符串 SS 后增加一个字符 cc，则 H(T)=(H(S+T)−H(S)×P∣T∣) mod m\text{H}(T)=(\text{H}(S+T) - \text{H}(S) \times P^{|T|}) \bmod m，其中 ∣T∣|T| 代表给字符串 TT 的长度。为保证时间复杂度，需要预处理 PP 的若干次方。

因为字符串哈希具有可加性与可减性，因此可使用前缀和处理字符串哈希问题。以 O(∣S∣)O(|S|) 的时间复杂度处理字符串 SS 的每个前缀的哈希值，用 O(1)O(1) 的时间复杂度查询字符串 SS 的任意一个字串的哈希值。

例题：【模板】字符串哈希

给定 NN 个字符串，第 ii 个字符串长度为 MiM_i，字符串内包含数字、大小写字母，大小写敏感，请求出 NN 个字符串中 共有多少个不同的字符串。

N≤10000N\leq 10000，Mi≈1000M_i \approx 1000，max⁡M≤1500\max M \leq 1500

样例输入：

5
abc
aaaa
abc
abcc
12345

样例输出：

4

解法：读入所有字符串，计算并存储其哈希值，排序并使用 unique 函数去重。请注意 hash 这个名字在 string 头文件中已经被定义。

[1]^{[1]} 字符集指可能出现在字符串中所有的字符组成的集合。

KMP

KMP 算法是由三位 dalao 共同提出的一种可以在线性时间复杂度内解决模式串匹配问题的算法，用于解决 SS 串在 TT 串中出现的次数和位置。

暴力算法时间复杂度为 O(∣S∣∣T∣)O(|S||T|)，显然不能通过大数据。

KMP 算法在程序上分为两步：

  1. 对字符串 SS 进行自我匹配，即求出 nextnext 数组，nextinext_i 表示 SS 中以 ii 为结尾的真子串，与 SS 的前缀能够匹配的最大长度。
  2. 对字符串 SS, TT 进行匹配，求出 ff 数组，fif_i 表示 TT 中以 ii 为结尾的子串，与 SS 的前缀能够匹配的最大长度。

KMP 算法的核心是 nextnext 数组，nextinext_i 的本质为前 ii 个字母的最长公共前后缀。即有 nexti=max⁡{j}next_i = \max\{j\}，其中 j<ij<i 且有 Si−j+1∼i=S1∼iS_{i-j+1 \sim i}=S_{1 \sim i}。

考虑 nextnext 数组的求法。

根据定义，有 next1=0next_1=0。假设 next1∼i−1next_{1 \sim i-1} 已经计算完毕，当计算 nextinext_i 时，即需要找到满足下面条件的 jj 的最大值。

  • j<ij<i
  • Si−j+1∼i=S1∼jS_{i-j+1 \sim i}=S_{1 \sim j}

我们称满足上述条件的 jj 为 nextinext_i 的候选项。

引理：若 j0j_0 是 nextinext_i 的一个候选项，则小于 j0j_0 的最大的 nextinext_i 的候选项是 nextj0next_{j_0}。

根据引理，当 nexti−1next_{i-1} 计算完毕后，即可得知所有 nexti−1next_{i-1} 的候选项，依次为 nexti−1next_{i-1}，nextnexti−1next_{next_{i-1}}，……。如果一个整数 jj 是 nextinext_i 的候选项，那么 j−1j-1 一定是 nexti−1next_{i-1} 的候选项。因此，计算 nextinext_i 的时候，只需把 nexti−1+1next_{i-1}+1，nextnexti−1+1next_{next_{i-1}}+1，…… 作为候选项即可。

由于 ff 与 nextnext 定义相似，只需参考 nextnext 数组求出的方法即可求出 ff 数组。

例题：【模板】KMP字符串匹配

给出字符串 S,TS,T，求 SS 在 TT 中出现的位置。最后一行输出 KMP 过程中求出的 nextnext 数组。

字符集为所有大写字母，且 1≤S,T≤1061 \le S,T \le 10^6。

样例输入：

ABABABC
ABA

样例输出：

1
3
0 0 1

解法：根据 KMP 算法求出 next,fnext,f 两个数组，如果 fi=∣S∣f_i=|S| 即为出现的终止位置。因为数组下标从 1 开始，所以字符串需使用 char 数组存储，输入时需从下标为 1 的地方开始输入。请注意 next 这个名字在 string 头文件中已经被定义。

字典树

字典树是一类 KK 叉树，KK 为字符集大小，用于字符串的快速检索。

每个节点都有 KK 个字符指针，分别对应字符集中的每个字符。在插入或检索字符串的过程中，扫描到字符 cc，就沿着对应的字符指针往下走即可。

一颗字典树在初始状态下只有一个空节点，其所有字符指针指向空。

  • 插入：插入前取指针 PP 指向字典树的根节点。如果 PP 指向的节点对应 S1S_1 的指针为空，则新建节点。将指针 PP 移动到该字符指针指向的节点。S2∼S∣S∣S_2 \sim S_{|S|} 同理。当字符串 SS 插入完毕，在最后的节点上打上终止标记即可。
  • 查找：依次扫描每个字符，如果对应的字符指针不存在，则字典树中没有这个字符串。如果当前节点有终止标记，则这个字符串曾经被插入到字典树中。

可以发现，关于字符串的数据都体现在边上，关于字符串终止与数目等附加信息的数据都体现在点上。

字典树的空间复杂度为 O(NC)O(NC)，其中 NN 代表结点个数，CC 代表字符集大小。

字典树的应用十分广泛，主要集中于前缀相关，亦可用于字符串集的字典序排序。

例题：【模板】字典树

给出 NN 个字符串，QQ 组询问。

每组询问给出一个字符串 SS，问 SS 是给出的 NN 个字符串中多少个字符串的前缀。

多测，TT 组测试数据。

字符集为所有大写字母、小写字母和 0-9，且 T,N,Q≤105T,N,Q \le 10^5，字符串长度 ≤3×106\le 3 \times 10^6。

样例输入：

1
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc

样例输出：

2
1
0

解法：将所有字符串插入字典树，给每个经过的点打标记，查询记录最后走到的点，输出最后走到的点的标记数。多测需要使用循环清空数组。

0-1 Trie 是一种特殊的字典树。

将一个二进制数补齐前导 00，视作字符串插入正常的 Trie。

可以用于一些位运算相关的题目。