字符串hash模板

发表于 | 更新于 | 分类于

思想

将每个字母映射成P进制数，一般进制数取131, 13331, 每个字母a - z相应的映射成 1 - 26,

这个数使用unsigned long long进行2^64的自动取模，避免了低效的mod运算。

求一段序列的hash值

令$ “axybb” = 1242522 (1, 24, 25, 2, 2)$
求xyb的hash值 $ axy = axyb - a * 123^{( 4 - (2 - 1) )} $, 将a左移进行对齐。

tips

可以多取几组p(可以取大质数)进行运算，如果都相等则为同一个串。

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6 + 5;
typedef unsigned long long ull;		//使用unsigned long long 进行自动溢出取模，减少低效的mod运算
ull p = 131, h[N], power[N];
char str[N];

ull get(int l, int r)	//计算子串hash值
{
    return h[r] - h[l - 1] * power[r - l + 1];	//类似于前缀和，则输入时下标从1开始，进行左对齐
}
int main()
{
    scanf("%s", str + 1);	//当l == 1时, l - 1 == 0的边界处理。
    power[0] = 1;
    int n = strlen(str + 1);
    for(int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * p + str[i] - 'a' + 1;			//p进制转换，ull自动取模
        power[i] = power[i - 1] * p;			//计算p乘方
    } 
    
    int m, l1, l2, r1, r2;
    cin >> m;
    while(m -- )
    {
        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);		//两个子串
        if(get(l1, r1) == get(l2, r2))		//相等判断
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

0%