1 条题解
-
0陈海斌 (阳光少年chen) LV 9 @ 2023-10-4 16:47:35
字符串哈希
#include <iostream> #include <cstring> #include <cstdio> using namespace std; typedef unsigned long long ull; #define int ull const int N=1e6+10; const int b=31; char s1[N],s2[N]; int power[N],H[N]; signed main(){ power[0]=1; for(int i=1;i<N;i++){ power[i]=power[i-1]*b; } int t; cin>>t; while(t--){ scanf("%s%s",s1+1,s2+1); int n=strlen(s1+1),m=strlen(s2+1); H[0]=0; for(int i=1;i<=m;i++){ H[i]=(H[i-1]*b+int(s2[i]-'A'+1)); } int s=0; for(int i=1;i<=n;i++){ s=s*b+int(s1[i]-'A'+1); } int ans=0; for(int i=0;i+n<=m;i++){ if(s==H[i+n]-H[i]*power[n]){ ans++; } } cout<<ans<<endl; } }
- 1
信息
- ID
- 376
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 56
- 已通过
- 23
- 上传者