题目链接

算法竞赛进阶指南-52.兔子与兔子

很久很久以前，森林里住着一群兔子。

有一天，兔子们想要研究自己的 DNA 序列。

我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 $26$ 个小写英文字母）。

然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。

注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入格式

第一行输入一个 DNA 字符串 $S$。

第二行一个数字 $m$，表示 $m$ 次询问。

接下来 $m$ 行，每行四个数字 $l_1, r_1, l_2, r_2$，分别表示此次询问的两个区间，注意字符串的位置从 $1$ 开始编号。

输出格式

对于每次询问，输出一行表示结果。

如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写）。

数据范围

$1 \le length(S),m \le 1000000$

输入样例：

aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

Method : 字符串Hash

标准的字符串前缀哈希题目，如果是第一次遇到字符串Hash的题目值得一做。

#include <string>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ULL;

const int N =1e6 + 7;
const int P = 131;

vector<ULL> p(N); // P的次幂

vector<ULL> get_prefix_hash(const string& s) {
    int n = s.size();
    vector<ULL> h(n + 1);
    h[0] = 0;
    p[0] = 1;
    for (int i = 1; i <= n; i ++) {
        h[i] = h[i - 1] * P + s[i - 1] - 'a' + 1;
        p[i] = p[i - 1] * P;
    }
    
    return h;
}

ULL get_substr_hash(const vector<ULL>& h, int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    string s;
    cin >> s;
    vector<ULL> h = get_prefix_hash(s);
    
    int m;
    cin >> m;
    while (m --) {
        int l1, r1, l2, r2;
        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
        if (get_substr_hash(h, l1, r1) == get_substr_hash(h, l2, r2)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(n)}$， 预处理前缀和需要$O(n)$，查询字串的时间复杂度是常数级$O(1)$。
• 空间复杂度：${O(N)}$，要花$O(n + 1)$的空间存储Hash前缀和，花$O(N)$的空间存储$P$的$N$次幂。