Pagini recente » Cod sursa (job #1487466) | Cod sursa (job #2021691) | Cod sursa (job #1895514) | Cod sursa (job #2021689) | Cod sursa (job #2107046)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
vector <int> H;
int n ,i,m,put[21];
char s[10000010];
char cuv[21];
int hash(char v[])
{
int val = 0,i;
for(i=m-1;i>=0;--i)
val = (val + put[m-i-1]*(v[i]-'a'));
return val;
}
void insert(int x)
{
H.push_back(x);
}
int find_hash(int x)
{
for(vector<int>::iterator it = H.begin();it!= H.end();it++)
if((*it) == x) return 1;
return 0;
}
int main()
{
FILE *f = fopen("abc2.in","r");
FILE *g = fopen("abc2.out","w");
fscanf(f,"%s",s);
fscanf(f,"%s",cuv);
n = strlen(s);m = strlen(cuv);
put[0]=1;
for(i=1;i<=20;i++)
put[i]=put[i-1]*3;
insert(hash(cuv));
while(fscanf(f,"%s",cuv) == 1)
{
insert(hash(cuv));
}
strncpy(cuv,s,m);
int x = hash(cuv),nr_cuv = 0;
for(i=m;i<n;i++)
{
if(find_hash(x)) nr_cuv++;
x = 3*x - (s[i-m] - 'a')*put[m] + (s[i] - 'a');
}
if(find_hash(x)) nr_cuv++;
fprintf(g,"%d",nr_cuv);
}