[模板]字符串哈希

[模板]字符串哈希_自然溢出

一.可求子串哈希值的字符串哈希:

对一个字符串进行这样的哈希操作,得到数组hs,hs[i]表示该字符串1~i部分的子串的哈希值.

利用这个数组可以表示这个字符串任意子串对应的哈希值.

// (自然溢出)
char s[1000];　　　　　　　　　　　　　　　　 // 将要进行操作的字符串
unsigned long long hs[1000], p[1000];    // 注意是unsigned long long, 这两个数组与字符串大小相同


    scanf("%s", s + 1);
    p[0] = 1;
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++) {
        hs[i] = hs[i - 1] * 131 + s[i] - 'a' + 1;    // hs[i] 即为字符串s在1~i部分的子串的哈希值,即前缀哈希值,如果有需要的话把这个循环倒着来一遍就可以得到后缀哈希值
        p[i] = p[i - 1] * 131;                        // p[i] 表示131^i
    }

    /* 
    采用如下方法表示l到r的子串的哈希值:
    hs[r] - hs[l - 1] * p[r - l + 1];
    若两段字符串的哈希值相等,则视其为相同字符串.这使得比较两端字符串的复杂度为O(1)
     */

一般来说,我们取p=131或p=13331,此时(自然溢出)Hash产生冲突的概率极低,...

除了极特殊构造的数据上,上述Hash算法很难产生冲突,一般情况下上述Hash算法完全可以出现在题目的标准解答中.

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　----<<指南>>

P2957 [USACO09OCT]Barn Echoes G

重复部分只会出现在一个字符串的后缀和另一个字符串的前缀出现,那么只需要以O(n)枚举重复部分长度即可.注意有两种情况要考虑.

理论上说,用strcmp可以达到与比较哈希值相同的效果,只是前者实现起来要处理一些细节,并且复杂度最坏情况下达到了O(n).哈希值算法在O(n)预处理后每次比较只需要O(1)时间.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int l1, l2, ans;
char s1[100], s2[100];
unsigned long long hs1[100], hs2[100], p[100];

int main() {
    scanf("%s%s", s1 + 1, s2 + 1);
    l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);
    p[0] = 1;
    for (int i = 1; i <= max(l1, l2); i++) {
        hs1[i] = hs1[i - 1] * 131 + s1[i] - 'a' + 1;
        hs2[i] = hs2[i - 1] * 131 + s2[i] - 'a' + 1;
        p[i] = 131 * p[i - 1];
    }

    for (int i = 1; i <= l1; i++)
        if (hs1[l1] - hs1[l1 - i] * p[i] == hs2[i])
            ans = i;
    for (int i = ans; i <= l2; i++)
        if (hs2[l2] - hs2[l2 - i] * p[i] == hs1[i])
            ans = i;
    printf("%d
", ans);

    return 0;
}

P2957

二.全字符串哈希

有时候只需要判断两个独立的字符串是否相等,就不需要大费周章了.

char s[1510];
unsigned long long hs[SIZE];　　　　// 可以存储SIZE个不同的字符串的哈希值

for (int i = 1; i <= n; i++) {
    scanf("%s", s);
/******计算字符串s的哈希值并存储到hs[i]中******/
    for (int j = 0; s[j]; j++) {
        hs[i] *= 131;
        hs[i] += s[j];　　　　　　　　// 相当于把字符用ASCII码转化为数字处理,也可以以特定的方式转化,有什么区别不好说
    }
/*****************************************/
}

P3370 【模板】字符串哈希

计算有多少个不同的字符串.把所有字符串转化为哈希值进行比较,由于哈希值是一个数字,就可以利用数字的特性比较:排序后逐个检查是否与上一个数字相等.

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, ans;
char s[1510];
unsigned long long hs[10010];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        for (int j = 0; s[j]; j++) {
            hs[i] *= 131;
            if (isalpha(s[j]))
                hs[i] += s[j] - 'a' + 10;
            else
                hs[i] += s[j] - '0';
        }
    }

    sort(hs + 1, hs + 1 + n);
    for (int i = 1; i <= n; i++)
        if (hs[i] != hs[i - 1]) ans++;
    printf("%d
", ans);

    return 0;
}

P3370