问题 A: 【 哈希和哈希表】子串查找

时间限制: 1 Sec 内存限制: 128 MB

题面 提交 状态

题目描述

这是一道模板题。

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

A中不同位置出现的B可重叠。

输入

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

输出

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

样例输入

复制样例数据

zyzyzyz

zyz

样例输出

3

提示

1≤A,B的长度≤106，A、B仅包含大小写字母。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 100;
const int temp = 71;
char a[maxn], b[maxn];
ll f[maxn];
int lena,lenb;
ll haxi[maxn],aa[maxn];
ll ans,cnt;
void fun(){
    f[1] = 71;
    for (int i = 2; i < maxn; i++)
        f[i] = f[i - 1] * temp;
}
int main() {
    fun();
    scanf("%s %s",a,b);
    lena =strlen(a);
    lenb = strlen(b);
    for(int i=lenb-1; i>=0; i--){
        ans=ans*temp;
        ans+=b[i];
    }
    for(int i=lena-1; i>=0; i--){
        haxi[i]=haxi[i+1]*temp;
        haxi[i]+=a[i];
    }
    for(int i=0;i<=lena-lenb;i++){
        aa[i]=haxi[i]-haxi[i+lenb]*f[lenb];
    }
    for(int i=0; i<=lena-lenb; i++){
        if(ans==aa[i]) cnt++;
    }
    printf("%lld\n", cnt);
    return 0;
}