字符串匹配--hash

思路：

先算出母串的hash值，再算出子串的hash值，利用差分的思想，计算出母串长度与子串长度相等的hash值，并进行判断，如果hash值相等，即可判断他们为相同的字符串，如果担心hash值冲突，即可加以一层判断来保证结果的准确性

时间复杂度O(n)

Code：

#include<iostream>
#include<vector>
#include<cmath>
#include<string.h>
#define ull unsigned long long//ull类型数据超过2^64自动取余
using namespace std;
const int X=13331;//进制数一般为13……31
const int N=1e6+5;
vector<ull> strhash;//动态定义母串hash数组
vector<ull> subhash;//动态定义子串hash数组
char str[N],sub[N];
ull x[N];//x[i]为X的i次方
int subl,strl;
void hash_code(char *s)//计算母串s的hash值
{
    strhash[0]=s[0];
    for(int i=1;i<strl;i++)
    {
        strhash[i]=strhash[i-1]*X+s[i];
    }
}
void init()//初始化x数组
{
    x[0]=1;
    for(int i=1;i<N;i++)
    x[i]=x[i-1]*X;
}
ull gethash(int left,int right)//获取字符串l到r区间的hash值
{
    return left?strhash[right]-strhash[left-1]*x[right-left+1]:strhash[right];
}

int main()
{
    cin>>str>>sub;
    strl=strlen(str);
    subl=strlen(sub);
    getnxt();
    getnxtv();
    strhash.resize(strl);//开辟字符串长度的空间
    subhash.resize(subl);//开辟空间
    init();
    hash_code(str);//计算母串str的hash值
    subhash[0]=sub[0];
    for(int i=1;i<subl;i++)
    {
        subhash[i]=subhash[i-1]*X+sub[i];//计算子串sub的hash值
    }
    for(int i=0;i<strl;i++)
    {
        if(gethash(i,i+subl-1)==subhash[subl-1]) cout<<i+1<<endl;//如果子串与母串的hash值相等，则证明子串与母串相等 ，并输出该子串在母串中的位置
    }
    return 0; 
}