【例题1】Oulipo 一本通

· · 个人记录

file:///C:/Users/lenovo/AppData/Local/Temp/WeChat%20Files/4d3b911157a7e500ab11bf74b8034dd.png

file:///C:/Users/lenovo/AppData/Local/Temp/WeChat%20Files/13e9db5314a75cf9fba8e661250b682.png

file:///C:/Users/lenovo/AppData/Local/Temp/WeChat%20Files/593b9ac480a1c18eeb3ccfafbfee398.png

以上三张图详细介绍了哈希算法

给出两个字符串s1,s2（(只有大写字母），求s1在s2中出现多少次。

例如：s1="ABA",s2="ABAABA",答案为2。

【输入】 输入T组数据，每组数据输出结果。

【输出】 如题述。

【输入样例】 3 BAPC BAPC AZA AZAAZAAZA VEEDI AVERDXIVYERDLAN 【输出样例】 1 3 0 【提示】 1≤s1的长度 ≤104​​ ，1≤s2的长度 ≤106​ 。

这道题就是哈希的模板题，求出对应的哈希值，挨个比较就可以

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
int T,b=769,n,m;
ULL powb[1000005]={1},sum[1000005],ans;
char s1[1000005],s2[1000005];
int main(){
    for(int i=1;i<=1000005-4;i++){
        powb[i]=powb[i-1]*b;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%s%s",s1+1,s2+1);//小 大
         n=strlen(s1+1);
         m=strlen(s2+1);
         ULL s=0;
         for(int i=1;i<=n;i++){
            s=s*b+(s1[i]-'A'+1);
         }
         for(int i=1;i<=m;i++){
            sum[i]=sum[i-1]*b+(s2[i]-'A'+1);
         }
         ans=0;
         for(int k=1;k<=m-n+1;k++){//k+k+n-1
            if(s==sum[k+n-1]-sum[k-1]*powb[n])ans++;
         }
         printf("%d\n",ans);
    }
}