Cod sursa(job #2295991)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 4 decembrie 2018 02:09:43
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb

#include <stdio.h>
#include <string.h>

#define N1 10000010
#define N2 1000000
#define M 999983

unsigned m , n , i , sol, pow, nr ;
char sir[N1], s[25];

struct hashh
{
	unsigned nod;
	hashh *next;
} *H[N2];

inline void add(unsigned sol)
{
	hashh *p;
	p = new hashh;
	p->nod = sol;
	p->next = H[sol%M];
	H[sol%M] = p;
}

inline int caut(unsigned sol)
{
	hashh *p;
	p=H[sol%M];
	while(p!=NULL)
	{
		if(p->nod==sol) return 1;
		p=p->next;
	}
	return 0;
}

int main()
{
	FILE *f = fopen("abc2.in","r");
	FILE *g = fopen("abc2.out","w");

	fgets ( sir, N1, f);
	n = strlen(sir)-1;
	if(sir[n] == '\n')
        n--;

	fgets(s, 25 , f);

	m = strlen(s)-1;
	if(s[m] == '\n')
        m--;
	sol = 0;
	for(i = 0; i <= m; i++)
		sol = sol*3 + s[i] - 'a';
	add(sol);

	while( fgets( s, 25, f ) != NULL )
	{
		if(!feof(f))
		{
			m = strlen(s)-1;
			if(s[m] == '\n')
                m--;
			sol = 0;
			for(i = 0; i <= m; i++)
				sol = sol*3 + s[i] - 'a';
			add(sol);
		}
	}

	sol = 0;
	for(i = 0; i <= m; i ++)
		sol = sol*3 + sir[i] - 'a';

	pow = 1;
	for(i = 1; i <= m; i++)
        pow *= 3;

	nr = 0;
	if(caut(sol))
        nr++;
	for(i = m+1; i <= n; i++)
	{
		sol = sol*3 - pow * (sir[i-m-1] - 'a') * 3 + (sir[i] - 'a');
		if(caut(sol))
            nr++;
	}

	fprintf(g, "%u", nr);

    fclose(f);
    fclose(g);

    return 0;
}