[编程笔记]-String_Hash字符串哈希

前言

这边首先推荐有需要滴去先瞅眼哈希表。
“[编程笔记]-Hash_Table哈希表”

（半夜写的，可能有点癫嘿嘿嘿）

简介

字符串哈希，就是对字符串进行哈希，达到快速储存和查询的目的。

实现

求HASH

这里要用到一种特殊的哈希方法：将字符串视作一个p进制数（p不一定，按题目要求来，一般就是所有可能出现的字符的个数，反正能让每个字符串独一无二就行），然后再对这个p进制数进行哈希操作。别的就一模一样了。

WARNING: 一般情况下不要映射成0！否则会造成哈希冲突！

WARNING: 这个算法下我们强的可怕！我们rp很nb！不考虑哈希冲突！

JINGYAN!!!: 当p取131或13331时，q（模）取2⁶⁴时，在99.99%的情况下，都不会出现冲突。

生活小寄巧：可用ull储存所有哈希值，这样就不用取模了，溢出就相当于取模了哈哈哈。

所以就易如反掌瓮中捉鳖轻轻松松探囊取物——h[i]=h[i-1]*p+str[i]

---

另外，这个方法有个小点可以注意一下：

如果我们求出了字符串每个前缀的hash值，就可以求出每个子串的hash值。

挂一个前缀和吧，虽然应该没有人会需要它“[编程笔记]-Partial_Sum前缀和”

公式：h[r]-h[l]*p^(r-l+1)

推导：举个例子，一个是”GRAY”，一个是”GRAYGOO”，要想得到”GOO”，肯定要用”GRAYGOO”减去”GRAY”左移三位得到的”GRAY “。当然我更希望去个GOO留GRAY，但为了方便理解还是放弃了。

啊对了其实这个小点是一个重点但是我懒得改前面的内容了所以就在前面加个着重符号吧(╹ڡ╹ )

例题

由于这算法本来是用来字符串匹配，但例题拿来子串匹配，不仅完美结合了原方法，还巧妙融合了前缀和问题（就是上面那个重点），所以就直接用这道毒瘤好题了。

AcWing841-字符串哈希

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const int N=1e5+5,P=131;

int n,m;
string str;
ull h[N],p[N];

int main(){
    cin.tie(0);
    cin>>n>>m>>str;
    str=' '+str;
    p[0]=1;
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+str[i];
    }
    int l1,r1,l2,r2;
    ull h1,h2;
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        h1=h[r1]-h[l1-1]*p[r1-l1+1];
        h2=h[r2]-h[l2-1]*p[r2-l2+1];
        cout<<(h1==h2?"Yes\n":"No\n");
    }
    return 0;
}

完结撒花o(￣︶￣)o

再这么熬下去我就成国家一级保护废物了