学习笔记：

详细讲解：https://blog.csdn.net/pengwill97/article/details/80879387

字符串hash：

利用unsigned long long的范围自然溢出，相当于自动对2^64−1取模

单Hash公式：

hash[i]=(hash[i−1])∗p+idx(s[i]) % mod

其中p和mod均为质数，且有p<mod，对于此种Hash方法，将p和mod尽量取大即可，这种情况下，冲突的概率是很低的。

双Hash公式：

hash1[i]=(hash1[i−1])∗p+idx(s[i]) % mod1

hash2[i]=(hash2[i−1])∗p+idx(s[i]) % mod2

hash结果为<hash1[n],hash2[n]>，这种Hash很安全。

获取子串的hash公式：

 

题目地址：http://poj.org/problem?id=3461

题目：

求模式串在文本串中出现的次数

 

解题思路：

p去13331，预处理出p^n，计算模式串的hash值，计算出文本串的hash数组，匹配模式串的hash值和文本串子串的hash值，统计答案。

时间复杂度：O(len(文本串))

 

ac代码：

#include<iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
typedef unsigned long long ll;
const int maxn = 1e6+5;
const ll p = 133331;
char s1[maxn], s2[maxn];
ll power[maxn], has[maxn];
void init() //预处理出p^n
{
    power[0] = 1;
    for(int i = 1; i < maxn; i++)
        power[i] = power[i - 1] * p; //unsigned long long 自然溢出
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    init();
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s", s1 + 1);
        scanf("%s", s2 + 1);
        int len1 = strlen(s1 + 1), len2  = strlen(s2 + 1);
        has[0] = 0;
        for(int i = 1; i <= len2; i++)
            has[i] = has[i - 1] * p + (ll)(s2[i] - 'A' + 1);
        ll sum = 0, ans = 0;
        for(int i = 1; i <= len1; i++)
            sum = sum * p + (ll)(s1[i] - 'A' + 1);
        for(int i = len1; i <= len2; i++)
        {
            ll tmp = has[i] - has[i - len1] * power[len1];
            if(sum == tmp) ans++;
        }
        printf("%llu\n", ans);
    }
    return 0;
}