1 条题解

  • 0

    字符串哈希

    #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
    上传者