Pagini recente » Cod sursa (job #2793819) | Cod sursa (job #1345133) | Cod sursa (job #569504) | Cod sursa (job #2836563) | Cod sursa (job #944813)
Cod sursa(job #944813)
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned int uint;
const uint hash_mod=666013;
vector<uint> H[hash_mod];
bool hash_find(const uint &hash_code)
{
uint h=hash_code%hash_mod;
for(auto &x : H[h])
if(x==hash_code)
return true;
return false;
}
char s[10000005];
char w[25];
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
uint hash_code=0,N,M,ans;
gets(s);
while(gets(w))
{
hash_code=0;
for(int i=0;w[i];i++)
hash_code=3u*hash_code+w[i]-'a';
if(!hash_find(hash_code))
H[hash_code%hash_mod].push_back(hash_code);
}
N=strlen(s);
M=strlen(w);
if(M>N)
{
printf("0\n");
return 0;
}
uint p=1;hash_code=0;
for(uint i=0;i<M;i++)
{
if(i) p=3u*p;
hash_code=3*hash_code+s[i]-'a';
}
if(hash_find(hash_code))
ans=1;
else
ans=0;
for(uint i=M;i<N;i++)
{
hash_code-=p*(s[i-M]-'a');
hash_code*=3u;
hash_code+=(s[i]-'a');
if(hash_find(hash_code))
ans++;
}
printf("%u\n",ans);
return 0;
}