Cod sursa(job #914696)

Utilizator bugyBogdan Vlad bugy Data 14 martie 2013 12:53:21
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#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;
}

int main()
{
	char s[dim],ss[dim2],str[dim2];;
	unsigned long x,X,u=1;
	int i, nr=0,n,lcuv;
	
	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;
}