兔子与兔子

题目描述

给定一个长度为 $n$ 的小写字母串 $S$ 和 $m$ 次询问。每次询问给出四个整数 $l_1, r_1, l_2, r_2$ （位置从 $1$ 开始），判断子串 $S[l_1..r_1]$ 与 $S[l_2..r_2]$ 是否完全相同，相同输出 Yes，否则输出 No。

思路

字符串哈希模板题：预处理前缀哈希 $h[i] = h[i-1] \times B + s_i$ （ $B=131$ ，模梅森素数 $2^{61}-1$ ）和 $B$ 的幂 $p[i]$ ，子串 $S[l..r]$ 的指纹为 $h[r] - h[l-1] \times p[r-l+1]$ ，每次询问 $O(1)$ 取出两个子串的指纹直接比较即可。注意 C++ 中减法可能得到负数，要手工加 $MOD$ 调整。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#!/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-01 11:39
# update_at: 2026-10-01 11:39

import sys

MOD = (1 << 61) - 1  # 梅森素数 2^61 - 1，模它时哈希值均匀，冲突概率可忽略
BASE = 131           # 哈希进制：字母集是 26 个小写字母，取比字符集大的底数


def prefix_hashes(s: str) -> tuple[list[int], list[int]]:
    """返回 (h, p)：h[i] 是前缀 s[:i] 的哈希值，p[i] 是 BASE^i mod MOD。"""
    h = [0] * (len(s) + 1)  # h[0] = 0，空串哈希
    p = [1] * (len(s) + 1)  # p[0] = 1，BASE^0
    for i, code in enumerate(map(ord, s), 1):
        h[i] = (h[i - 1] * BASE + code) % MOD
        p[i] = p[i - 1] * BASE % MOD
    return h, p


def sub_hash(h: list[int], p: list[int], l: int, r: int) -> int:
    """取出区间 [l, r] 的哈希值：去掉前缀 [1, l-1] 贡献的高位。"""
    return (h[r] - h[l - 1] * p[r - l + 1]) % MOD


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    s = next(data).decode()
    query_count = int(next(data))

    h, p = prefix_hashes(s)

    # 4m 个数字依次取 4 个就是一组 (l1, r1, l2, r2)，zip 能对齐同一个迭代器
    out = [
        'Yes' if sub_hash(h, p, l1, r1) == sub_hash(h, p, l2, r2) else 'No'
        for l1, r1, l2, r2 in zip(*[iter(map(int, data))] * 4)
    ]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
 * 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-06 11:32
 * update_at: 2026-10-06 11:32
 */
#include <cstdio>
#include <cstring>

typedef long long ll;

// 字符串哈希模板题：判断两个子串是否完全相同
const ll MOD = (1LL << 61) - 1; // 梅森素数 2^61-1，哈希值分布均匀，冲突概率可忽略
const ll BASE = 131;            // 哈希进制，比字符集大
const int MAXN = 1000005;

char s[MAXN];    // 输入字符串，下标从 1 开始
ll h[MAXN];      // h[i] = 前缀 s[1..i] 的哈希值（看成 BASE 进制数）
ll p[MAXN];      // p[i] = BASE^i mod MOD，用于对齐高位
ll ans[MAXN];    // 暂存每个询问的回答，0 表示 No，1 表示 Yes

// 取出子串 s[l..r] 的哈希值：减掉前缀 [1, l-1] 贡献的高位
ll sub_hash(int l, int r) {
    ll v = h[r] - h[l - 1] * p[r - l + 1] % MOD;
    if (v < 0) v += MOD; // 减法可能出现负数，手工调整到 [0, MOD)
    return v;
}

int main() {
    // 快读：m 可达 1e6，用 getchar 手写读入
    static char buf[MAXN];
    scanf("%s", buf + 1);
    int n = strlen(buf + 1);

    // 预处理前缀哈希和 BASE 的幂
    h[0] = 0;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = (h[i - 1] * BASE + buf[i]) % MOD;
        p[i] = p[i - 1] * BASE % MOD;
    }

    int m;
    scanf("%d", &m);
    for (int q = 1; q <= m; q++) {
        int l1, r1, l2, r2;
        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
        // 子串相同等价于指纹相同
        ans[q] = (sub_hash(l1, r1) == sub_hash(l2, r2));
    }

    // 统一输出，避免 1e6 次 printf 拖慢速度
    for (int q = 1; q <= m; q++) {
        if (ans[q]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

目录

题目描述

思路

参考代码