关键在于选取合适的 和
,试了好多数最后才对。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+6;
char t[N],s[N];
const int mod=2147483587;
ll Hash,por;
int base=25165843,ans[1010];
unordered_map<ll,int>mp;
void init(int len)
{
Hash=0;
for(int i=1;i<=len;i++)
Hash=(Hash*base%mod+t[i])%mod;
mp[Hash]=1;
por=1;
for(int i=1;i<len;i++)
por=por*base%mod;
for(int i=1;i<=len;i++)
{
Hash=(Hash-t[i]*por%mod+mod)%mod;
Hash=(Hash*base%mod+t[i])%mod;
mp[Hash]=1;
}
}
int main()
{
scanf("%s",t+1);
int len=strlen(t+1);
init(len);
int n,let=len;
ll hs;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
len=strlen(s+1);
if(len<let)
continue;
hs=0;
for(int j=1;j<=let;j++)
hs=(hs*base%mod+s[j])%mod;
if(mp[hs]==1) ans[i]++;
for(int j=let+1;j<=len;j++)
{
hs=(hs-s[j-let]*por%mod+mod)%mod;
hs=(hs*base%mod+s[j])%mod;
if(mp[hs]==1) ans[i]++;
}
}
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}

京公网安备 11010502036488号