Cod sursa(job #306256)

Utilizator FlorianFlorian Marcu Florian Data 20 aprilie 2009 09:50:00
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<cstdio>
#include<string>
using namespace std;
#define MAX_L 10000004
#define MAX_C 24
#define Mod 666013
#define B 3
char s[MAX_L];
int n;
int L, N;
int nr;
struct Tabela
{
	int nr;
	Tabela *urm;
};
Tabela *H[Mod];
void insert(int x)
{
	Tabela *q;
	int h = x % Mod;
	for(q=H[h];q;q=q->urm) if(q->nr == x) return;
	Tabela *p = new Tabela;
	p->urm = H[h]; p->nr  = x;
	H[h] = p;
}
int find(int x)
{
	Tabela *q;
	int h = x%Mod;
	for(q=H[h];q;q=q->urm) if(q->nr == x) return 1;
	return 0;
}
int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	scanf("%s\n",s+1);
	char cuv[MAX_C]; int i;
	int hash, P, pr = 1;
	s[0] = '!';
	L = strlen(s) - 1;
	while(!feof(stdin))
	{
		memset(cuv,0,sizeof(cuv));
		scanf("%s\n",cuv+1);
		cuv[0] = '!';
		N = strlen(cuv) - 1;
		hash = 0; P = 1;
		for(i=1;i<=N;++i)
		{
			hash = hash + P*(cuv[i] - 'a');
			P = P*B;
		}
		insert(hash);
	}
	P = 1; hash = 0;
	for(i=L-N+1;i<=L;++i) 
	{
		hash += P*(s[i]-'a');
		P*=B;
	}
	pr = P / B;
	i = L-N;
	nr += find(hash);
	for(i = L-N;i>0;--i)
	{
		hash -= pr * (s[i+N] - 'a');
		hash *= B;
		hash += (s[i] - 'a');
		nr += find(hash);
	}
	printf("%d\n",nr);
	return 0;
}