Pagini recente » Cod sursa (job #2519511) | Cod sursa (job #1914334) | Cod sursa (job #1529370) | Cod sursa (job #1939523) | Cod sursa (job #914710)
Cod sursa(job #914710)
#include<stdio.h>
#include<string.h>
//#include "hashtable.h"
#define dim 10000005
#define dim2 25
#define MOD 500013
struct list_elem{
int info;
list_elem *prev, *next;
};
class Hash_table{
public:
struct list_elem *pfirst;
void add(int x)
{
struct list_elem *nod;
nod = new struct list_elem;
nod -> info = x;
nod ->prev = NULL;
nod ->next = pfirst;
if(pfirst != NULL)
pfirst -> prev = nod;
pfirst = nod;
}
struct list_elem *find(int x)
{
struct list_elem *nod;
nod = pfirst;
while(nod != NULL)
{
if(nod -> info == x)
return nod;
nod = nod -> next;
}
return NULL;
}
Hash_table(){
pfirst = NULL;
}
~Hash_table(){}
};
unsigned long getval(char * s,int n)
{
int i;
unsigned long val = 0;
for(i=0;i<n;i++)
val = val * 3 + s[i] - 'a';
return val;
}
char s[dim],ss[dim2],str[dim2];
unsigned long x,X,u=1;
int i, nr=0,n,lcuv;
int main()
{
FILE *f, *g;
f=fopen("abc2.in","r");
g=fopen("abc2.out","w");
Hash_table H[MOD];
fgets(s, dim , f); //citesc textul
n=strlen(s); //lungimea textului
s[n-1]='\0';
n--;
fscanf(f,"%s\n",ss); //citesc primul cuvant
lcuv = strlen(ss); //lungimea cuvintelor
x = getval(ss,lcuv); //ii calculez valoarea
H[x % MOD].add(x); //il adaug in tabela
while( !feof(f) )
{
fscanf(f,"%s\n",ss);
x = getval(ss,lcuv);
H[x % MOD].add(x);
}
//solve:
struct list_elem *p;
for(i = 0; i < lcuv; i++)
str[i] = s[i];
X = getval(str,lcuv);
p = H[X % MOD].find( X );
if(p != NULL)
nr++;
for(i=1;i<lcuv;i++)
u*=3;
for(i=lcuv; i<= n; i++)
{
X = X - u * (s[i-lcuv] - 'a');
X = X * 3 + (s[i] - 'a');
p = H[X % MOD].find( X );
if(p != NULL)
nr++;
}
fprintf(g,"%d\n",nr);
fclose(f);
fclose(g);
return 0;
}