Cod sursa(job #612749)

Utilizator maritimCristian Lambru maritim Data 9 septembrie 2011 22:41:00
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<vector>
using namespace std;

#define M 90907
#define MaxN 10000010
#define ll long long

typedef vector<unsigned int>::iterator it;

vector<unsigned int> H[M];
char S[MaxN];
int ln,LN,NR;

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

void citire(void)
{
	char A[27];
	unsigned int a;
	FILE *f = fopen("abc2.in","r");
	
	fgets(S,sizeof(S),f);
	while(!feof(f))
	{
		fgets(A,sizeof(A),f);
		ln = strlen(A);
		a = Func(A);
		H[a%M].push_back(a);
	}
	
	fclose(f);
}

inline int ExistString(unsigned int a)
{
	int b = a%M;
	for(it i = H[b].begin();i<H[b].end();i++)
		if(*i == a)
			return 1;
	return 0;
}

void solve(void)
{
	for(int i=0;S[i];i++)
	{
		unsigned int a = 0;
		for(int j=0;j<ln-1;j++)
			a = a*3 + S[i+j]-'a';
		NR += ExistString(a);
	}
}

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