Pagini recente » Cod sursa (job #1929716) | Cod sursa (job #1349685) | Cod sursa (job #1361051) | Cod sursa (job #1705616) | Cod sursa (job #3036438)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define MOD1 10007
#define hash1 3
char A[1000001],B[1000001];
vector <unsigned int> hashtable[10007];
unsigned int sol,p1,p2,hashB1,hashA1,hashB2,hashA2,n,m;
bool search(unsigned int h)
{
unsigned int poz=h%MOD1;
for(unsigned int i=0; i<hashtable[poz].size(); ++i)if(hashtable[poz][i]==h)return 1;
return 0;
}
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
unsigned int i;
scanf("%s", A);
while(scanf("%s", B)!=EOF)
{
m=strlen(B);
hashB1=0;
for(i=0; i<m; ++i)
{
hashB1=((hashB1*hash1)+(B[i]-'a'));
}
if(!search(hashB1))hashtable[hashB1%MOD1].push_back(hashB1);
}
p1=p2=1;
n=strlen(A);
for(i=0; i<m; ++i)
{
hashA1=((hashA1*hash1)+(A[i]-'a'));
if(i>0)
{
p1=(p1*hash1);
}
}
if(search(hashA1))++sol;
for(i=m; i<n; ++i)
{
hashA1=((hash1*(hashA1-((A[i-m]-'a')*p1))))+(A[i]-'a');
if(search(hashA1))++sol;
}
printf("%d\n", sol);
return 0;
}