滚动Hash

假设字符串$C=c_1*c_2*...c_m$，定义Hash函数$H(C)=(C_1*b^{m-1}+C_2*b^{m-2}+...C_m*b^{0})mod\; h$

从k开始长为|m|的子串的hash值转移到从k+1开始长为|m|的字串的hash值的转移公式为 :$$H(S[k+1..k+m]=(H(S[k..k+m-1])b-s_kb^m+s_{k+m}$$

基数使用1e7以上的素数减少冲突，使并且用$ull$自然溢出代替取模运算，滚动Hash的期望复杂度为$O(n+m)$。

给出字符串S和T，求S在T中出现的次数。

AcCode：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef unsigned long long ull;

const ull B = 100000007;//Hash基数

int n;

char w[10010],t[1000010];

int main(){

    scanf("%d",&n);

    while(n--){

        scanf("%s%s",w,t);

        int lw=strlen(w),lt=strlen(t);

        ull wh=0,th=0,base=1;

        //计算W和T串从第一位开始的长度为lenw的Hash值

        for(int i=0;i<lw;i++)

            wh=wh*B+w[i],th=th*B+t[i];

        //计算base的lenw次方，用于Hash转移

        for(int i=0;i<lw;++i)base*=B;

        int ans=0;

        for(int i=0;i+lw<=lt;++i){

            if(wh==th)ans++;

            if(i+lw<lt)th=th*B+t[i+lw]-t[i]*base;//这里减法可能会溢出，但是利用无符号数的自然溢出就无需加上一个模数了

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

# 滚动Hash

滚动Hash

最新文章

热门文章