子串查找（哈希 算法）

题目描述

这是一道模板题。

给定一个字符串A和一个字符串B，求 B在 A中的出现次数。 A和B
中的字符均为英语大写字母或小写字母。A中不同位置出现的B可重叠。

输入格式

输入共两行，分别是字符串A和字符串B。
输出格式

输出一个整数，表示B在A中的出现次数。

样例

样例输入

zyzyzyz
zyz

样例输出

3

数据范围与提示

1<=A,B的长度 <=10^6， A、 B仅包含大小写字母。

题意：

求在字符串A中字符串B出现的次数，位置可重叠

思路：

先计算模式串的哈希值，再计算出主串每一段的哈希值，循环对比主串某段的哈希值与模式串是否相等，相等出现的次数就加1

代码：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
char a[1000010];
char s[1000010];
ull ha[1000010];
int main()
{
    ull hs=0,pow1=1;
    scanf("%s",a);
    scanf("%s",s);
    int b=123,i;//b值是任意定义，素数即可
    int la=strlen(a);
    int ls=strlen(s);
    for(i=0;i<ls;i++)//计算模式串的哈希值
    {
        hs=hs*b+(ull)(s[i]);
        pow1*=b;
    }
    ha[0]=a[0];
    for(i=1;i<la;i++)
        ha[i]=ha[i-1]*b+(ull)(a[i]);//计算主串每一段的哈希值
    int k=0;
    for(i=ls-1;i<la;i++)
    {
        if(i-ls<0&&ha[i]==hs)//长度和模式串相等
            k++;
        else if(ha[i]-ha[i-ls]*pow1==hs)
            k++;
    }
    printf("%d\n",k);
    return 0;
}