Pagini recente » Cod sursa (job #2132358) | Cod sursa (job #1507073) | Borderou de evaluare (job #173192) | Cod sursa (job #472867) | Cod sursa (job #2295335)
#include<stdio.h>
#include<string.h>
#define M 393241
#define NMAX 10000005
FILE *fin,*fout;
struct node
{
unsigned long long info;
node *urm;
};
node *hashtable[M];
unsigned long long hfunction(unsigned long long x)
{
return x%M;
}
int searchnode(unsigned long long value)
{
node *head = hashtable[hfunction(value)];
while (head != NULL && head->info != value)
{
head = head->urm;
}
if (head != NULL)
{
return 1;
}
return 0;
}
void addnode(unsigned long long value)
{
node *first = new node;
first->info = value;
first->urm = hashtable[hfunction(value)];
hashtable[hfunction(value)] = first;
}
char sir[NMAX],cuvant[30];
unsigned long long lcuvant,lsir,i;
int main()
{
fin=fopen("abc2.in","r");
fout=fopen("abc2.out","w");
fgets(sir,10000005,fin);
lsir=strlen(sir);
if(sir[lsir-1]=='\n'){sir[lsir-1]=0;lsir--;}
fgets(cuvant,30,fin);
lcuvant=strlen(cuvant);
if(cuvant[lcuvant-1]=='\n'){cuvant[lcuvant-1]=0;lcuvant--;}
unsigned long long value=0;
for (i = 0; i <= lcuvant - 1; i++)
{
value = 3 * value + (cuvant[i] - 'a');
}
addnode(value);
while (fgets(cuvant,30,fin)!=NULL)
{
unsigned long long value = 0;
for (i = 0; i <= lcuvant - 1; i++)
{
value = 3 * value + (cuvant[i] - 'a');
}
if (searchnode(value) == 0)
{
addnode(value);
}
}
unsigned long long p = 1;
for (i = 1; i <= lcuvant - 1; i++)
{
p = p * 3;
}
unsigned long long rh = 0;
for (i = 0; i <= lcuvant - 1; i++)
{
rh = 3 * rh + sir[i] - 'a';
}
int sol=0;
sol = sol + searchnode(rh);
lsir = strlen(sir);
for (i = lcuvant; i <= lsir - 1; i++)
{
rh = rh - p * (sir[i - lcuvant] - 'a');
rh = 3 * rh + (sir[i] - 'a');
sol = sol + searchnode(rh);
}
fprintf(fout,"%d",sol);
fclose(fin); fclose(fout);
return 0;
}