字符串哈希（模板）

54 阅读 0 评论 36 点赞

我是靠谱客的博主高挑黑夜，最近开发中收集的这篇文章主要介绍字符串哈希（模板），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

字符串哈希就是将一个字符串通过一定方式转化成一个数据，便于与其他字符串进行比较是否相同。

要将一个字符串s转化成一个数字，我们可以通过进制转化方式进行，即将一个字符串转化位P进制数（这里的P一般取131或13331）如：

char s[] = {'a','b','c','d'};
//则该字符串即为 abcd 左边为高位，右边为低位，转为P进制数 ans(ans初始值为0)即可表示为
for(int i = 0 ;i < strlen(s);i++)
	ans = ans * P + s[i];

同时又因为我们要尽量避免发生冲突，所以我们要进行取模，这里为了尽可能的不发生冲突，我们对 2^64 进行取模，但是如果每次计算都要取模，就不免显得有些麻烦，所以我们可以如下处理方式：

#define ULL unsigned long long
ULL ans;//用ULL 来定义ans，当ans大于 2^64 时，会自动进行取模

洛谷上有一道模板题：【模板】字符串哈希

#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long

const int P = 131;
const int N = 10010;
ULL h[N];//创建一个ULL类型的数组，用以存储每一个字符串的哈希值
char s[N];
int n,m;

ULL get(char s[])
{
    ULL len = strlen(s);
    ULL ans = 0;
    for(ULL i = 1 ;i <= len ;i++)
    {   
        ans = ans * P + s[i];//计算哈希值
    }
    return ans;
}

int main()
{
    cin>>n;
    for(int i = 1 ;i <= n ;i++)
    {
        scanf("%s",s);
        h[i] = get(s);
    }
    sort(h + 1,h + n + 1);//不同的字符串哈希值相同的可能性很小，所以排序之后，如果前后哈希值相同，则字符串相同
    for(int i = 1;i <= n;i++)
    {
        if(h[i] != h[i + 1])
            m++;
    }
    cout<<m<<endl;
    return 0;
}

此外，字符串哈希还可以用来确定一个字符串中是否有相同的的子串。

为了确定是否有相同的子串，我们就需要设法求出我们要判断的子串的哈希值。因此我们可以利用一个 ULL 类型的数组 h[N] 来表示从下标 1 到下标 i 的子串（该字符串从下标 1 开始存储）的哈希值。我们就可以借助这个数组来求出下标 l 到 r 的子串的哈希值

如字符串ABCDEFG
         L
s1:A B C D E F G
s1:A B C D E F G
             R
在上面的字符串s1中 下标 1~L-1 的哈希值为 A * P^2 + B * P + C = h[L-1]
在下面的字符串s1中 下标 1~R 的哈希值为 A * P^5 + B * P^4 + C * P^3 + D * P^2 + E * P + F = h[R]
若要求子串DEF的哈希值，则要用下面s1中的ABCDEF的哈希值 - ABC的哈希值
即为 h[R] - h[L - 1] * p^3
因此可得结论，若要求子串L到R的哈希值ans
则 ans = h[R] - h[L - 1] * p^(R - L + 1)

如题：

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

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

输入格式

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

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

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

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

输出格式

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

每个结果占一行。

数据范围

1≤n,m≤10^5

输入样例：

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

输出样例：

Yes
No
Yes

题解：

#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long

int n,m;
const int N = 1e5 +10,P = 131;
char str[N];
ULL p[N],h[N];

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

int main()
{
    scanf("%d%d%s",&n,&m,str + 1);
    p[0] =1;
    for(int i = 1 ;i <= n ;i++)
    {
        p[i] = p[i - 1] * P;//预先处理P^n
        h[i] = h[i - 1] * P + str[i];//求出前缀的哈希值
    }
    int l1,r1,l2,r2;
    while(m--)
    {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1) == get(l2,r2))
            puts("Yes");
        else puts("No");
    }
}