文章评分

GitHub跳转原题关系图返回列表

双模滚动哈希把每个长度为 m 的子串压成一个整数,排序后计数互不相同的哈希值个数。

OJ: roj

题目 ID: 1691

难度:普及+/提高-

标签:字符串哈希排序python

创建: 2026-10-07 15:37

更新: 2026-10-07 15:37

形式化题目

给定长度为 nn 的小写字母串 s=s1s2⋯sns = s_1 s_2 \cdots s_n 和整数 mm,考察全部 n−m+1n - m + 1 个长度为 mm 的连续子串

sisi+1⋯si+m−1(1⩽i⩽n−m+1),s_i s_{i+1} \cdots s_{i+m-1} \qquad (1 \leqslant i \leqslant n - m + 1),

求其中本质不同的子串个数(出现多次的同一个串只算一次)。

正解

思路

先把问题变成"重复计数"。 直接把每个子串切成字符串塞进集合,写法最短:

python
len({s[i:i + m] for i in range(n - m + 1)})

它在 n,m⩽2×105n, m \leqslant 2 \times 10^5 下不行:最坏情况(例如 m≈n/2m \approx n/2)要搬运 O(nm)O(nm) 个字符,时间到 101010^{10} 量级,切片本身还要额外内存。瓶颈有两处——比较两个子串要逐字符,保存子串要存整段字符。只要能把每个子串换成"一次比较就够"的整数,两个瓶颈同时消失,这就是哈希。

滚动哈希:给每个子串一个整数指纹。 把字母 cc 映射成数字 d=c−’a’+1d = c - \texttt{'a'} + 1(映射到 11 而不是 00,防止 a、aa 这类串因前导零变成同一个数),把整个串看作 BB 进制数并取模:

pre[i]=(pre[i−1]⋅B+di) mod p,pre[0]=0.\mathrm{pre}[i] = \left( \mathrm{pre}[i-1] \cdot B + d_i \right) \bmod p, \qquad \mathrm{pre}[0] = 0 .

于是子串 si⋯si+m−1s_{i} \cdots s_{i+m-1} 的哈希是

hash(i)=(pre[i+m−1]−pre[i−1]⋅Bm) mod p.\mathrm{hash}(i) = \left( \mathrm{pre}[i+m-1] - \mathrm{pre}[i-1] \cdot B^{m} \right) \bmod p .

这个式子只做一次乘法、一次减法,与 mm 无关;BmB^m 预先算一遍即可。相邻两个窗口的哈希还能 O(1)O(1) 互推(乘 BB、加新字符、减旧字符),所以全部窗口哈希可以在 O(n)O(n) 内一次扫出。

为什么必须用两套模数。 单模哈希可能把两个不同的串映到同一个值(碰撞)。每个窗口两两比较,共约 n2/2≈2×1010n^2/2 \approx 2 \times 10^{10} 对,用模 10910^9 级别的单模,碰撞概率不可忽略。取两个模数 p1=109+7p_1 = 10^9 + 7、p2=998244353p_2 = 998244353,把一对哈希打包成

key=h1⋅p2+h2,\mathrm{key} = h_1 \cdot p_2 + h_2 ,

它不超过 101810^{18},long long 装得下,而且这个打包是单射:两个窗口的 key 相等,当且仅当两套哈希都相等。于是"两两比较两个哈希值"退化成"比较一个整数",碰撞概率降到 (n−m+1)2p1p2≈4×10101018<10−7\dfrac{(n-m+1)^2}{p_1 p_2} \approx \dfrac{4\times10^{10}}{10^{18}} < 10^{-7}。

排序去重代替集合。 得到 n−m+1n-m+1 个 key 后排序,扫一遍数出相邻不同的个数即为答案。C++ 里排序比哈希表快得多;Python 里直接用 set 更短,效果一样(集合里每个 key 只留一份,答案就是集合大小)。

以样例 1(s=aaaabs = \texttt{aaaab},m=3m = 3)为例,取 p=109+7p = 10^9+7、B=131B = 131:

窗口 子串 pre[i−1]\mathrm{pre}[i-1] pre[i+2]\mathrm{pre}[i+2] 窗口哈希 是否新串
i=1i=1 aaa 0 17293 17293 是
i=2i=2 aaa 1 17294 17293 否(与第 1 个相同)
i=3i=3 aab 131 17294 17294 是

前两个窗口字符完全相同、哈希也完全相同,第三个窗口只改了末位字母,哈希恰好差 1;去重后答案为 2,与样例一致。这也说明哈希的用途只是判断相等,不需要保留子串内容。

代码

Python 版:

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++ 版(同一算法,把哈希打包成整数后排序计数):

cpp
/**
 * 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;
}

复杂度

  • 时间:预处理前缀哈希与 BmB^m 为 O(n)O(n),求全部窗口哈希为 O(n)O(n),排序为 O(nlog⁡n)O(n \log n),答案为 O(nlog⁡n)O(n \log n)。C++ 版在最大测试点(n=200000n = 200000)实测 0.021 s、峰值 10 MB。
  • 空间:前缀哈希、幂、窗口键各 O(n)O(n),共约 5n5n 个 64 位整数,O(n)O(n),实测峰值 10 MB(限时 256 MB)。
  • 正确性来源:哈希是随机化的单射近似,双模打包后的碰撞概率小于 10−710^{-7};若要求严格确定性,可以改用后缀自动机(统计状态数)或后缀数组,但本题双模哈希已足够。

总结

  • 判等才是重点:题目只问"两个子串是否相同",从不问"子串是什么",所以用一个整数指纹替换整段字符是最自然的抽象。
  • 滚动哈希的骨架是 hash(i)=pre[i+m−1]−pre[i−1]⋅Bm\mathrm{hash}(i) = \mathrm{pre}[i+m-1] - \mathrm{pre}[i-1] \cdot B^m,字母映射到 1∼261 \sim 26 可避免前导零歧义;BmB^m 只算一次,所以单次取子串哈希与 mm 无关。
  • 必须用两套模数:本题要比较的子串对数达 101010^{10} 量级,单模哈希的碰撞概率不可接受;把两个余数按 h1⋅p2+h2h_1 \cdot p_2 + h_2 打包成一个 64 位整数,既是单射又让相等判断只需一次整数比较。
  • 去重靠排序或集合:C++ 排序 O(nlog⁡n)O(n \log n) 且内存友好,Python 用 set 更短,两者都是把"哪些子串相同"交给哈希键,不再逐字符比较。
  • 这类"统计本质不同子串"的题有确定性替代解法(后缀自动机、后缀数组 + LCP),复杂度同为 O(nlog⁡n)O(n \log n) 或更低,但代码量远大于双模哈希,双模哈希是性价比最高的写法。