【题解】「POJ3461」Oulipo（字符串Hash）

本文主要是介绍【题解】「POJ3461」Oulipo（字符串Hash），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

【题目描述】
给定两个串S1，S2，只有大写字母，求S1在S2中出现了几次。
【输入】
输入T组数据，每组数据两个串S1，S2.
strlen(S1)<=10^4
strlen(S2)<=10^6，
【输出】
对于每组数据，输出答案。
【样例输入】

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

【样例输出】

1
3
0

算法分析

字符串Hash。

参考程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define b 31
using namespace std; 
unsigned int n,Hash[1000100],p[1000100];
char s1[10100],s2[1000100];
int main()
{scanf("%d",&n);p[0]=1;for(int i=1;i<=1000000;i++)		//预处理p的i次方p[i]=p[i-1]*b;for(int i=1;i<=n;i++){int ans=0;scanf("%s%s",s1,s2);int len1=strlen(s1),len2=strlen(s2);Hash[0]=s2[0];for(int i=1;i<len2;i++)Hash[i]=Hash[i-1]*b+s2[i];  //计算主串的滚动Hash int s=s1[0];for(int i=1;i<len1;i++)s=s*b+s1[i];        //计算匹配串Hash //  cout<<s<<endl;for(int i=0;i+len1-1<len2;i++)   //枚举起点i，长度为len1的子串，判断是否与匹配串匹配 {if(i==0 &&s==Hash[i+len1-1]) {ans++; continue;}if(s==Hash[i+len1-1]-Hash[i-1]*p[len1])ans++;//  cout<<Hash[i+len1-1]-Hash[i-1]*p[len1]<<endl;}printf("%d\n",ans);} return 0; 
}  

这篇关于【题解】「POJ3461」Oulipo（字符串Hash）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---