Cod sursa(job #612730)

Utilizator maritimCristian Lambru maritim Data 9 septembrie 2011 21:42:21
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<stdio.h>
#include<string.h>
#include<malloc.h>

#define M 1000321
#define MaxN 10000010
#define ll long long

typedef struct _nod
{
	char info[27];
	struct _nod *adr;
} nod;

nod *H[M];
char S[MaxN];
int ln,LN,NR;

int Func(char A[])
{
	int a = 1;
	for(int i=0;i<ln-1;i++)
		a = (a*3 + A[i]-'a')%M;
	return a;
}

void add(char A[])
{
	int a = Func(A);
	nod *nou = (nod*)malloc(sizeof(nod));
	strcpy(nou->info,A);
	nou->adr = H[a];
	H[a] = nou;
}

void citire(void)
{
	char A[27];
	FILE *f = fopen("abc2.in","r");
	
	fgets(S,sizeof(S),f);
	while(!feof(f))
	{
		fgets(A,sizeof(A),f);
		ln = strlen(A);
		add(A);
	}
	
	fclose(f);
}

int ExistString(char A[27])
{
	int a = Func(A);
	nod *p = H[a];
	while(p)
		if(strcmp(p->info,A) == 0)
			return 1;
		else
			p = p->adr;
	return 0;
}

void solve(void)
{
	LN = strlen(S);
	char A[21];
	for(int i=0;i<=LN-ln;i++)
	{
		for(int j=0;j<ln-1;j++)
			A[j] = S[i+j];
		A[ln-1] = '\n';
		A[ln] = '\0';
		NR += ExistString(A);
	}
}

int main()
{
	FILE *g = fopen("abc2.out","w");
	
	citire();
	solve();
	fprintf(g,"%d ",NR);
	
	fclose(g);
	return 0;
}