双模滚动哈希把每个长度为 m 的子串压成一个整数,排序后计数互不相同的哈希值个数。
OJ: roj
题目 ID: 1691
难度:普及+/提高-
标签:字符串哈希排序python
创建: 2026-10-07 15:37
更新: 2026-10-07 15:37
形式化题目
给定长度为
求其中本质不同的子串个数(出现多次的同一个串只算一次)。
正解
思路
先把问题变成"重复计数"。 直接把每个子串切成字符串塞进集合,写法最短:
len({s[i:i + m] for i in range(n - m + 1)})它在
滚动哈希:给每个子串一个整数指纹。 把字母 a、aa 这类串因前导零变成同一个数),把整个串看作
于是子串
这个式子只做一次乘法、一次减法,与
为什么必须用两套模数。 单模哈希可能把两个不同的串映到同一个值(碰撞)。每个窗口两两比较,共约
它不超过 long long 装得下,而且这个打包是单射:两个窗口的 key 相等,当且仅当两套哈希都相等。于是"两两比较两个哈希值"退化成"比较一个整数",碰撞概率降到
排序去重代替集合。 得到 set 更短,效果一样(集合里每个 key 只留一份,答案就是集合大小)。
以样例 1(
| 窗口 | 子串 | 窗口哈希 | 是否新串 | ||
|---|---|---|---|---|---|
aaa |
0 | 17293 | 17293 | 是 | |
aaa |
1 | 17294 | 17293 | 否(与第 1 个相同) | |
aab |
131 | 17294 | 17294 | 是 |
前两个窗口字符完全相同、哈希也完全相同,第三个窗口只改了末位字母,哈希恰好差 1;去重后答案为 2,与样例一致。这也说明哈希的用途只是判断相等,不需要保留子串内容。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:37
# update_at: 2026-10-07 15:37
import sys
from itertools import accumulate
MOD1 = 1000000007 # 第一套哈希的模数
MOD2 = 998244353 # 第二套哈希的模数
BASE1 = 131 # 第一套哈希的进制
BASE2 = 137 # 第二套哈希的进制
def window_keys(text: str, m: int) -> set[int]:
"""返回全部长度为 m 的子串的哈希键集合:同一个键多次出现只留一份。
前缀哈希 pre[i] 是 text[:i] 的 BASE 进制值,于是窗口 text[i:i + m] 的哈希是
(pre[i + m] - pre[i] * BASE ** m) mod MOD;两套模哈希打包成一个整数当集合键,
打包满足单射,所以键相同就当且仅当两套哈希都相同。
"""
length = len(text)
window_count = length - m + 1 # 窗口个数,即子串的总个数
digits = [ord(ch) - 96 for ch in text] # 'a' 记成 1,避免前导零的歧义
pre1 = list(accumulate(digits, lambda acc, c: (acc * BASE1 + c) % MOD1, initial=0))
pre2 = list(accumulate(digits, lambda acc, c: (acc * BASE2 + c) % MOD2, initial=0))
factor1 = pow(BASE1, m, MOD1) # BASE1 ** m,窗口公式里的固定系数
factor2 = pow(BASE2, m, MOD2) # BASE2 ** m,作用同上
hashes1 = ((pre1[i + m] - pre1[i] * factor1) % MOD1 for i in range(window_count)) # 各窗口第一套哈希
hashes2 = ((pre2[i + m] - pre2[i] * factor2) % MOD2 for i in range(window_count)) # 各窗口第二套哈希
both_hashes = zip(hashes1, hashes2)
# h1 * MOD2 + h2 是单射打包:键相等当且仅当两套哈希都相等,于是集合天然完成去重
return {hash1 * MOD2 + hash2 for hash1, hash2 in both_hashes}
def solve() -> None:
tokens = iter(sys.stdin.buffer.read().split())
n, m = int(next(tokens)), int(next(tokens)) # n 就是文章长度,只用于对照题面格式
text = next(tokens).decode()
print(len(window_keys(text, m)))
if __name__ == "__main__":
solve()C++ 版(同一算法,把哈希打包成整数后排序计数):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 15:37
* update_at: 2026-10-07 15:37
*/
// main.cpp:文章评分,统计长度 m 的本质不同子串个数。
// 与 main.py 同一算法:双模滚动哈希把每个窗口压成一个 64 位整数,排序去重后计数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD1 = 1000000007LL; // 第一套哈希的模数
const ll MOD2 = 998244353LL; // 第二套哈希的模数
const ll BASE1 = 131LL; // 第一套哈希的进制
const ll BASE2 = 137LL; // 第二套哈希的进制
const int MAXN = 200005;
// 一个前缀(或一个窗口)在两套模数下的哈希值,打包在一起避免平行数组
struct HashPair {
ll first; // 模 MOD1 的哈希
ll second; // 模 MOD2 的哈希
};
ll n, m; // 文章长度、需要统计的子串长度
char text[MAXN]; // text[1..n] 存放文章
HashPair power[MAXN]; // power[i] = (BASE1^i mod MOD1, BASE2^i mod MOD2)
HashPair pre[MAXN]; // pre[i] 是 text[1..i] 的两套前缀哈希
ll win_key[MAXN]; // win_key[i] 是第 i 个窗口的双模哈希压成的单个整数
int main() {
if (scanf("%lld %lld", &n, &m) != 2) return 0;
scanf("%s", text + 1);
power[0].first = 1;
power[0].second = 1;
for (int i = 1; i <= n; i++) {
power[i].first = power[i - 1].first * BASE1 % MOD1;
power[i].second = power[i - 1].second * BASE2 % MOD2;
ll digit = text[i] - 'a' + 1; // 'a' 记成 1,避免前导零带来的歧义
pre[i].first = (pre[i - 1].first * BASE1 + digit) % MOD1;
pre[i].second = (pre[i - 1].second * BASE2 + digit) % MOD2;
}
// 窗口 text[i..i+m-1] 的哈希 = pre[i+m-1] - pre[i-1] * BASE^m,
// 两个模数各约 1e9,打包成 h1 * MOD2 + h2 后不超过 1e18,一个 ll 装得下,
// 而且打包是单射:键相等当且仅当两套哈希都相等。
ll window_count = 0;
for (int i = 1; i + m - 1 <= n; i++) {
int right_end = i + m - 1;
ll hash1 = (pre[right_end].first - pre[i - 1].first * power[m].first % MOD1 + MOD1) % MOD1;
ll hash2 = (pre[right_end].second - pre[i - 1].second * power[m].second % MOD2 + MOD2) % MOD2;
win_key[++window_count] = hash1 * MOD2 + hash2;
}
sort(win_key + 1, win_key + window_count + 1);
ll ans = 0; // 排序后相邻比较,键第一次出现就说明遇到一个新的子串
for (ll i = 1; i <= window_count; i++) {
if (i == 1 || win_key[i] != win_key[i - 1]) ans++;
}
printf("%lld\n", ans);
return 0;
}复杂度
- 时间:预处理前缀哈希与
为 ,求全部窗口哈希为 ,排序为 ,答案为 。C++ 版在最大测试点( )实测 0.021 s、峰值 10 MB。 - 空间:前缀哈希、幂、窗口键各
,共约 个 64 位整数, ,实测峰值 10 MB(限时 256 MB)。 - 正确性来源:哈希是随机化的单射近似,双模打包后的碰撞概率小于
;若要求严格确定性,可以改用后缀自动机(统计状态数)或后缀数组,但本题双模哈希已足够。
总结
- 判等才是重点:题目只问"两个子串是否相同",从不问"子串是什么",所以用一个整数指纹替换整段字符是最自然的抽象。
- 滚动哈希的骨架是
,字母映射到 可避免前导零歧义; 只算一次,所以单次取子串哈希与 无关。 - 必须用两套模数:本题要比较的子串对数达
量级,单模哈希的碰撞概率不可接受;把两个余数按 打包成一个 64 位整数,既是单射又让相等判断只需一次整数比较。 - 去重靠排序或集合:C++ 排序
且内存友好,Python 用 set更短,两者都是把"哪些子串相同"交给哈希键,不再逐字符比较。 - 这类"统计本质不同子串"的题有确定性替代解法(后缀自动机、后缀数组 + LCP),复杂度同为
或更低,但代码量远大于双模哈希,双模哈希是性价比最高的写法。