题目

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int t,b=7;
char s[10001+10],c[1000001+10];
unsigned long long p[10001];
unsigned long long sum[100001];
unsigned long long ans=0,h=1<<31;
int main()
{
	for (int i=1;i<=100001;i++)
	    p[i]=p[i-1]*b;
	cin>>t;
	while (t--){
		ans=0;
		scanf("%s%s",s+1,c+1);
		int lenc=strlen(c+1);
		int lens=strlen(s+1);
		sum[0]=0;
		for (int i=1;i<=lenc;i++)  
		    sum[i]=(sum[i-1]*b+(unsigned long long)(c[i]-'A'+1))%h;
		unsigned long long a=0;
		for (int i=1;i<=lens;i++){
			a=(a*b+(unsigned long long)(s[i]-'A'+1))%h;
		}
		for(int i=0;i<=lenc-lens;i++)
             if(a==sum[i+lens]-sum[i]*p[lens]) ans++;
		
		cout<<ans<<endl;
	}
    return 0;
}

正解

#include<bits/stdc++.h>
using namespace std;

int T;
int n,m;
int ans;
char s1[10000+10],s2[1000000+10];
unsigned long long power[1000000+10];
unsigned long long H[1000000+10];
unsigned long long s,b=27,h=1<<31;


int main()
{
    power[0]=1;
    for(int i=1;i<=1000000;i++)
    power[i]=power[i-1]*b;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s%s",s1+1,s2+1);
        n=strlen(s1+1);m=strlen(s2+1);
        H[0]=0;
        for(int i=1;i<=m;i++) H[i]=(H[i-1]*b+(unsigned long long)(s2[i]-'A'+1))%h;
        s=0;
        for(int i=1;i<=n;i++) s=(s*b+(unsigned long long)(s1[i]-'A'+1))%h;
        ans=0;
        for(int i=0;i<=m-n;i++)
         if(s==H[i+n]-H[i]*power[n]) ans++;
        printf("%d\n",ans);
    }
    return 0;
}

错哪了？