Cod sursa(job #107055)

Utilizator megabyteBarsan Paul megabyte Data 19 noiembrie 2007 10:03:26
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define INF "abc2.in"
#define OUF "abc2.out"
#define LMAX 10000002
#define HMAX 1046527 
#define SG 1
#define GG 2
#define sz(x) x.size()

using namespace std;

char s[LMAX];
int n,m,sz;

struct nod
{
	unsigned k;
	nod *next;
};

struct hnod
{
	nod *p;
	void pb(unsigned arg)
	{
		
		nod *op,*q;
		op=new nod;
		op->k=arg;op->next=NULL;			
		if(p==NULL) p=op;
		else
		{
			if(arg<p->k)
			{
				op->next=p;
				p=op;
				
			}
			else
			{
				q=p;
				while(q->next&&arg>q->next->k) q=q->next;

				if(arg!=q->k)
				{
					op->next=q->next;
					q->next=op;
				}
			}	
		}		
	}
	bool hset(unsigned arg)
	{
		nod *q;
		q=p;
		if(p==NULL) return false;
		if(arg==p->k) return true;
		else
		{

			while(q->next&&arg>=q->next->k) q=q->next;
			if(q->k==arg) return true;
			else return false;
		}
	}
	void print()
	{
		nod *q;
		q=p;
		while(q){ printf("%d ",q->k);q=q->next;}
		printf("\n");
	}
}mh[HMAX];

inline unsigned mctod(char c)
{
	switch(c)
	{
		case 'b': return 1;
		case 'c': return 2;
		default : return 0;
	}
}

inline unsigned hmap(char *v)
{
	unsigned key=0;
	while(*v&&*v!='\n')
	{
		key=key*3+mctod(*v);
		++v;
	}
	return key;
}

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	int sol=0,i,j;
	char word[32]={0};
	unsigned k,delta,tla[32];
	fgets(s,LMAX,in);
	n=strlen(s);--n;

	tla[0]=1;
	for(i=1;i<32;++i) tla[i]=tla[i-1]*3;//printf("%lld ",tla[i]);}

	
	fgets(word,32,in);
	m=strlen(word);--m;
	k=hmap(word);	//			printf("%lld ",k);
	mh[k%HMAX].pb(k);
	while(fgets(word,32,in)) {k=hmap(word);mh[k%HMAX].pb(k);}//	printf("%lld ",k);}
//	printf("\n\n");
	

//	mh[0].print();
//	mh[1].print();
//	mh[2].print();
	
	
	i=0;
	for(j=0;j<m;++j) word[j]=s[j];
	k=hmap(word);		//printf("%lld ",k);
	if(mh[k%HMAX].hset(k)) ++sol;
	i=1;	
	while(i+m-1<n)
	{
		delta=tla[m-1]*mctod(s[i-1]);
		k=(k-delta)*3+mctod(s[i+m-1]);//		printf("%lld ",k);
//		delta=tla[m-1]*mctod(s[i]);
		if(mh[k%HMAX].hset(k)) ++sol;
		++i;
	}

	fprintf(out,"%d",sol);
	fclose(in);fclose(out);
	return 0;
}