资讯详情

【题目来源】

洛谷：P3370 【模板】字符串哈希 - 洛谷

【题目描述】

如题，给定 \(N\) 个字符串（第 \(i\) 个字符串长度为 \(M_i\)，字符串内包含数字、大小写字母，大小写敏感），请求出 \(N\) 个字符串中共有多少个不同的字符串。

【输入】

第一行包含一个整数 \(N\)，为字符串的个数。

接下来 \(N\) 行每行包含一个字符串，为所提供的字符串。

【输出】

输出包含一行，包含一个整数，为不同的字符串个数。

【输入样例】

5
abc
aaaa
abc
abcc
12345

【输出样例】

4

【核心思想】

1. 问题分析：给定 \(N\) 个字符串，要求统计其中不同的字符串有多少个。由于字符串长度和数量都可能很大，直接两两比较的时间复杂度为 \(O(N^2 \cdot M)\)，无法接受。字符串哈希的核心思想是将每个字符串映射为一个整数（哈希值），使得不同的字符串大概率对应不同的哈希值，从而将字符串比较转化为整数比较。

2. 算法选择：

   • 多项式哈希（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)\) 的整数比较

3. 关键步骤：

   • 读取输入：字符串数量 \(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 即为不同字符串的数量（在哈希无冲突的前提下）

4. 时间/空间复杂度：

   • 时间复杂度：\(O(N \cdot M + N \log N)\)，其中 \(M\) 为平均字符串长度。计算所有哈希值 \(O(N \cdot M)\)，排序 \(O(N \log N)\)，去重 \(O(N)\)
   • 空间复杂度：\(O(N)\)，存储 \(N\) 个哈希值

5. 字符串哈希的核心思想：

   • 将字符串映射为指纹：多项式哈希将变长字符串转化为定长整数，使得字符串的相等判断转化为整数比较，复杂度从 \(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