【题目来源】
洛谷：P3370 【模板】字符串哈希 - 洛谷
【题目描述】
如题，给定 \(N\) 个字符串（第 \(i\) 个字符串长度为 \(M_i\)，字符串内包含数字、大小写字母，大小写敏感），请求出 \(N\) 个字符串中共有多少个不同的字符串。
【输入】
第一行包含一个整数 \(N\)，为字符串的个数。
接下来 \(N\) 行每行包含一个字符串，为所提供的字符串。
【输出】
输出包含一行，包含一个整数，为不同的字符串个数。
【输入样例】
5
abc
aaaa
abc
abcc
12345
【输出样例】
4
【核心思想】
-
问题分析：给定 \(N\) 个字符串，要求统计其中不同的字符串有多少个。由于字符串长度和数量都可能很大，直接两两比较的时间复杂度为 \(O(N^2 \cdot M)\)，无法接受。字符串哈希的核心思想是将每个字符串映射为一个整数（哈希值），使得不同的字符串大概率对应不同的哈希值，从而将字符串比较转化为整数比较。
-
算法选择：
- 多项式哈希（Polynomial Hashing）：将字符串 \(s = c_0 c_1 \ldots c_{m-1}\) 看作一个 \(x\) 进制数，哈希值为 \(H(s) = (c_0 \cdot x^{m-1} + c_1 \cdot x^{m-2} + \ldots + c_{m-1}) \bmod y\)。通过递推式 \(H_i = (H_{i-1} \cdot x + c_i) \bmod y\) 可在 \(O(m)\) 时间内计算
- 自然溢出哈希：使用
unsigned long long（64位无符号整数），利用其自然溢出等价于对 \(2^{64}\) 取模。这种方式无需显式取模运算，效率更高，且冲突概率极低 - 排序 + 去重：计算所有字符串的哈希值后排序，再用
unique统计不同哈希值的数量，将 \(O(N^2)\) 的字符串比较降为 \(O(N \log N)\) 的整数比较
-
关键步骤：
- 读取输入：字符串数量 \(N\) 和 \(N\) 个字符串 \(s_1, \ldots, s_N\)
- 计算哈希值（
myhash(s)）：- 初始化
code = 0 - 选定基数 \(x\)（通常为 \(131\)、\(13131\)、\(13331\) 等）和模数 \(y\)（大质数，或利用
unsigned long long自然溢出） - 遍历字符串每个字符：\
code = code * x + s[i]（若显式取模则再加% y） - 返回
code作为该字符串的哈希值
- 初始化
- 存储与排序：将所有哈希值存入数组
a[1..N]，调用sort(a + 1, a + n + 1) - 去重统计：
ans = unique(a + 1, a + n + 1) - (a + 1)，得到不同哈希值的数量 - 输出答案：
ans即为不同字符串的数量（在哈希无冲突的前提下）
-
时间/空间复杂度：
- 时间复杂度：\(O(N \cdot M + N \log N)\)，其中 \(M\) 为平均字符串长度。计算所有哈希值 \(O(N \cdot M)\)，排序 \(O(N \log N)\)，去重 \(O(N)\)
- 空间复杂度：\(O(N)\)，存储 \(N\) 个哈希值
-
字符串哈希的核心思想：
- 将字符串映射为指纹：多项式哈希将变长字符串转化为定长整数，使得字符串的相等判断转化为整数比较，复杂度从 \(O(M)\) 降为 \(O(1)\)
- 滚动哈希的递推性质：\(H(s[0..i]) = H(s[0..i-1]) \cdot x + s[i]\)，支持从左到右 \(O(1)\) 递推计算，也支持 \(O(1)\) 计算任意子串哈希值（需预处理前缀哈希和幂次）
- 哈希冲突与防御：
- 单哈希：选一个合适的基数和模数，冲突概率已很低
- 双哈希：用两组不同的 \((x_1, y_1)\) 和 \((x_2, y_2)\) 计算两个哈希值，组成二元组，几乎不可能冲突
- 自然溢出：利用
unsigned long long的 \(2^{64}\) 模运算，省去取模操作，常数更小
- 基数选择的经验值：\(131\)、\(13131\)、\(13331\)、\(233\) 等，通常避开 \(2\) 的幂次和字符串长度的倍数
- 适用于：字符串去重、字符串匹配、子串比较、回文判断、最长公共子串等字符串问题
【解题思路】
【算法标签】
普及- #字符串哈希
【代码详解】
#include <bits/stdc++.h>
using namespace std;typedef unsigned long long ull; // 定义无符号长整型别名int n, ans; // n: 字符串数量, ans: 不重复字符串数量
string s; // 临时存储输入的字符串
ull a[10005]; // 存储字符串的哈希值/*** 计算字符串的哈希值* @param s 输入字符串* @return 字符串的哈希值*/
ull myhash(string s)
{ull code = 0; // 初始化哈希值ull x = 131; // 哈希基数ull y = 140814840257324663; // 大质数模数// 计算字符串的哈希值for (int i = 0; i < s.size(); i++){code = (code * x + (ull)s[i]) % y; // 多项式哈希算法}return code;
}int main()
{// 输入字符串数量cin >> n;// 计算每个字符串的哈希值并存储for (int i = 1; i <= n; i++){cin >> s;a[i] = myhash(s);}// 对哈希值进行排序sort(a + 1, a + n + 1);// 计算不重复的哈希值数量ans = unique(a + 1, a + n + 1) - (a + 1);// 输出不重复字符串的数量cout << ans;return 0;
}
【运行结果】
5
abc
aaaa
abc
abcc
12345
4