字符串哈希

题目链接

AcWing 841. 字符串哈希

概念&理解

即将一个字符串转化成一个整数，并保证字符串不同,得到的哈希值不同。
这样就可以直接判断两个子字符串是否相同，不用一个一个字符判断。

哈希方法

这里暂时使用 unsigned long long 自然溢出法，即直接用 ull 存哈希，相当于对 2^64-1 取模
比如对于一个长度为n的字符串s
设定p为一个素数（通常为13，133，1333，2333）
$hash[0] = 0$
$hash[1] = hash[0] * p + s[1] = s[1]$
$hash[2] = hash[1] * p + s[2] = s[1] * p^1 + s[2]$
$hash[3] = hash[2] * p + s[3] = s[1] * p^2 + s[2] * p^1 + s[3]$
$hash[4] = hash[3] * p + s[4] = s[1] * p^3 + s[2] * p^2 + s[3] * p^1 +s[4]$
......
$hash[n] = hash[n-1] * p + s[n] = s[1] * p^{n-1} + s[2] * p^{n-2} +…+ s[n-1] * p^1 + s[n]$

求出一个子字符串的哈希值：O(1)

则字符串 $s[3]$ 到 $s[4]$ 的$hash$是$s[3] * p^1 + s[4]$
用类似前缀和思想：即 $哈希[4] - 哈希[3-1]$，但要想得到上式则需先将$hash[3-1] * p^{4 - (3 - 1) = 2}$
得到公式：求字符串 $s[L]$ 到 $s[R]$ 的哈希是 $哈希[R] - 哈希[L-1]$
即： $hash[R] - hash[L-1] * p^{R-L+1}$

具体实现

1.预处理出$h[i]$和$p[i]$，这里p使用13
2.get函数返回指定子串的$hash$

#include<iostream>
using namespace std;
const int N = 1e5+10, M = 13;
typedef unsigned long long ull;

ull p[N],h[N];
char str[N];
int n,m,l1,r1,l2,r2;

void Hash(){
    p[0]=1;//注意p^0=1
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*M+str[i];
        p[i]=p[i-1]*M;
    }
}

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

int main(){

    cin>>n>>m>>str+1;
    Hash();//预处理
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))puts("Yes");
        else puts("No");
    }
    return 0;
}