子串查找

https://loj.ac/problem/103

题目描述

  给定一个字符串A和一个字符串B,求B在A中的出现次数。A和B中的字符均为英语大写字母或小写字母。

思路

  显然这是道字符串匹配题我,我们可以用KMP求解。但这里我主要想介绍一种更简单的方法:字符串Hash。我们去一个基数b,把字符串看做b进制的数。而为了尽快求出一定长度的字符串的Hash值,我们可以用滚动Hash。这一过程可以用递推完成:H(C,k+1)=H(C,k)*b + ck+1。因此我们可以求出从通过以下式子求出从k开始长n的字符串Hash值:

                H(C’)=H(C,k+n)-H(C,k)*bn

  那么做一遍就行了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull b=131;
char s1[1000005],s2[1000005];
ull power[1000005],sum[1000005]; 
int main() 
{
    scanf(" %s %s",s1+1,s2+1);
    power[0]=1;
    for(int i=1;i<1000000;i++)
        power[i]=power[i-1]*b;
    int m=strlen(s1+1),n=strlen(s2+1);
    for(int i=1;i<=m;i++)
        sum[i]=sum[i-1]*b+s1[i];
    ull s=0,ans=0;
    for(int i=1;i<=n;i++)
        s=s*b+s2[i];
    for(int i=0;i<=m-n;i++)
        if(s==sum[i+n]-sum[i]*power[n])ans++;
    printf("%lld",ans);
    return 0;
}

 

上一篇:A Horrible Poem


下一篇:门票