跳到主要内容

字符串哈希

【模板】字符串哈希​

题目描述​

https://www.luogu.com.cn/problem/P3370

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

友情提醒：如果真的想好好练习哈希的话，请自觉。

输入格式​

第一行包含一个整数 NN，为字符串的个数。

接下来 NN 行每行包含一个字符串，为所提供的字符串。

输出格式​

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

样例输入 #1​

5
abc
aaaa
abc
abcc
12345

样例输出 #1​

4

提示​

对于 30%30\% 的数据：N≤10N\leq 10，Mi≈6M_i≈6，Mmax≤15Mmax\leq 15。

对于 70%70\% 的数据：N≤1000N\leq 1000，Mi≈100M_i≈100，Mmax≤150Mmax\leq 150。

对于 100%100\% 的数据：N≤10000N\leq 10000，Mi≈1000M_i≈1000，Mmax≤1500Mmax\leq 1500。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为aaaa,abc,abcc,12345{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

思路​

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低

小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

把每个字符串的值计算出来，放到vector容器中，然后再排序去重，剩下的大小就是不同的个数。

代码​

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;

const int P = 13331, N = 1010;

ull f(string s) {
    s = " " + s;
    ull res = 0;
    for (int i = 1; i <= s.size() - 1; i++) {
        res = res * P + s[i];
    }
    return res;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n;
    cin >> n;
    vector<ull> a;
    while (n--) {
        string s;
        cin >> s;
        a.push_back(f(s));
    }
    std::sort(a.begin(), a.end());
    a.erase(std::unique(a.begin(), a.end()), a.end());
    cout << a.size() << endl;
    return 0;
}

字符串哈希​

题目​

给定一个长度为 nn 的字符串，再给定 m$$m 个询问，每个询问包含四个整数 l1,r1,l2,r2l_1, r_1, l_2, r_2，请你判断 [l1,r1][l_1, r_1] 和 [l2,r2][l_2, r_2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式​

第一行包含整数 nn 和 mm，表示字符串长度和询问次数。

第二行包含一个长度为 nn 的字符串，字符串中只包含大小写英文字母和数字。

接下来 mm 行，每行包含四个整数 l1,r1,l2,r2l_1, r_1, l_2, r_2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 11 开始编号。

输出格式​

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围​

1≤n,m≤1051 \le n, m \le 10^5

输入样例：​

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

输出样例：​

Yes
No
Yes

思路​

把字符串看成一个P进制数，计算每一段的值.需要预处理出来.

image-20230517200145659

代码​

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;
const int P = 13331;
const int N = 1e5 + 10;
ull p[N], h[N];

ull get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    s = " " + s;
    p[0] = 1, h[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    while (m--) {
        int l1, l2, l3, l4;
        cin >> l1 >> l2 >> l3 >> l4;
        cout<<(get(l1,l2)==get(l3,l4)?"Yes":"No")<<endl;
    }
    return 0;
}
0%