字符串哈希详解

哈希函数的选取

通常我们采用的是多项式 Hash 的方法，对于一个长度为 l 的字符串 s 来说，我们可以这样定义多项式 Hash 函数：其中，M需要选择一个素数（至少要比最大的字符要大），b 是一个比最大字符大的整数。（ASCII码值比较）

之所以选择这样的哈希函数，不仅是因为它不容易产生哈希碰撞(就是不同的字符串出现相同的值的情况)，还因为利用这个函数可以比较方便求出子串的哈希值

(1)先求前缀子串：s[0],s[0,1],s[0~2],...,s[0~n-1]的哈希值：类似与求前缀和。

例如s=“abcde”。基数为base, 先不考虑取模。

hash[0]=a
        hash[1]=a*base+b=hash[0]*base+s[1]
        hash[2]=a*base*base+b*base+c=(a*base+b)*base+c=hash[1]*base+s[2]
        hash[3]=a*base*base*base+b*base*base+c*base+d
                =(a*base*base+b*base+c)*base+d
                =hash[2]*base+s[3]
则：hash[0]=s[0]，i>0时：hash[i]=hash[i-1]*base+s[i]

(2)求任意一子串s\[ l~r ]的哈希值h,带入上方的哈希函数得到：

h= s[l]* base^{r-l} + s[l+1]* base^{r-l-1} + ... +s[r]
hash[l-1]=s[0] * base^{l-1}+ s[1]*base^{l-2}+...+s[l-1]
hash[r]= s[0] * base^r+ s[1]* base^{r-1}+...+ s[l-1] * base^{r-l+1}+s[l] * base^{r-l}+...+ s[r]
故h=hash[r] - hash[l-1] * base^{r-l+1}

int base = 131;
vector<ull> hash(n+1);
vector<ull> mul(n+1);
mul[0]=1;

for(int i=1;i<=n;i++){
	hash[i] = hash[i-1]*base+(ull)text[i-1]; //hash[i]：前i个字母的哈希值
    mul[i] = mul[i-1]*base;     //mul[i]:base的i次方
}

M的选取

(1)将b和M尽量取大即可,越大值域越大，冲突越小。

M 最大可以取多大？    unsigned long long的最大值：2^64-1，刚好由于C++语言的特性，对于unsigned long long  a，若变量a保存的值超过2^64-1时，会自动对  2^64-1取余。所以所有变量的值都用unsigned long long即可，这种方法叫做自然取余法

2）双Hash法：一个字符串用不同的Base和MOD，hash两次，将这两个结果用一个二元组表示，作为一个总的Hash结果。
相当于我们用不同的Base和MOD，进行两次单Hash方法操作，然后将得到的结果，变成一个二元组结果，这样子，我们要看一个字符串，就要同时对比两个Hash 值，这样出现冲突的概率就很低了。MOD选择两个10^9级别的质数，只有模这两个数都相等才判断相等,目前暂时没有办法能卡掉这种写法（除了卡时间让它超时），比较好用的两个质数：

b(进制)的选取

关于进制的选择实际上非常自由，大于所有字符对应的数字的最大值，不要含有模数的质因子(那还模什么)，比如一个字符集是a到z的题目，选择27、**131**、19260817 都是可以的。（131比较好用）

注意:
1. 只针对上述哈希函数有可以求子串哈希值这样的特性，其他哈希函数不一定有
2. 不要把任意字符对应到数字0，比如假如把a对应到数字0，那么将不能只从Hash结果上区分ab和b，因为都是b的值，一般而言，把a-z对应到数字1-26比较合适。也可以直接使用字母本身对应的ASCll码值求哈希值。

双哈希法求不重复字符串的示例：

//双哈希法求不重复字符串个数
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;
ull base=131;

struct data
{
    ull x,y;
}a[10010];

char s[10010];
int n,ans=1;
ull mod1=19260817;
ull mod2=19660813;

//求两种不同哈希值
ull hash1(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod1;
    return ans;
}


ull hash2(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod2;
    return ans;
}

bool comp(data a,data b)
{
    return a.x<b.x;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s);
        //求每个字符串对应得两个哈希值，放到a数组里
        a[i].x=hash1(s);  
        a[i].y=hash2(s);
    }
	//排序后分别对比相邻的前一个字符串两个哈希值是否相同，不相同则为不同字符串
    sort(a+1,a+n+1,comp);
    for (int i=2;i<=n;i++)
        if (a[i].x!=a[i-1].x || a[i-1].y!=a[i].y)
            ans++;
    printf("%d\n",ans);
}

[不同的循环子字符串](https://leetcode.cn/problems/distinct-echo-substrings/) 1837
[子串的最大出现次数](https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring/)

[2261. 含最多 K 个可整除元素的子数组](https://leetcode.cn/problems/k-divisible-elements-subarrays/)查找数组中最多k个可以整除p的元素的子数组个数(长度相同，元素也相同的子数组是相同的子数组)