题意
这是一道模板题.
给定一个字符串 A 和一个字符串 B , 求 B 在 A 中的出现次数. A 和 B 中的字符均为英语大写字母或小写字母.
A 中不同位置出现的 B 可重叠.
分析
参照 https://www.cnblogs.com/jklover/p/10185164.html 的题解.
此题用 hash 做的话, 只需求出字符串 b 的 hash 值, 在字符串 a 中 O(n) 枚举每个长度等于 | b | 的子串, 判断 hash 值是否相等即可.
时间复杂度: 线性.
代码
- #include<bits/stdc++.h>
- #define rg register
- #define il inline
- #define co const
- template<class T>il T read()
- {
- rg T data=0;
- rg int w=1;
- rg char ch=getchar();
- while(!isdigit(ch))
- {
- if(ch=='-')
- w=-1;
- ch=getchar();
- }
- while(isdigit(ch))
- {
- data=data*10+ch-'0';
- ch=getchar();
- }
- return data*w;
- }
- template<class T>il T read(rg T&x)
- {
- return x=read<T>();
- }
- typedef unsigned long long ull;
- co int N=1e6+1;
- co ull Base=233;
- ull Hash[N],Pow[N];
- char a[N],b[N];
- int n,m;
- ull calchash(int l,int len)
- {
- return Hash[l+len-1]-Hash[l-1]*Pow[len];
- }
- int main()
- {
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- scanf("%s%s",a+1,b+1);
- n=strlen(a+1),m=strlen(b+1);
- ull hashb=0;
- for(int i=1;i<=m;++i)
- hashb=hashb*Base+b[i];
- Pow[0]=1;
- for(int i=1;i<=n;++i)
- {
- Hash[i]=Hash[i-1]*Base+a[i];
- Pow[i]=Pow[i-1]*Base;
- }
- int ans=0;
- for(int i=1;i+m-1<=n;++i)
- if(calchash(i,m)==hashb)
- ++ans;
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2935740.html