Cod sursa(job #99156)

Utilizator megabyteBarsan Paul megabyte Data 10 noiembrie 2007 22:27:21
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.45 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
using namespace std;

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

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

inline long long hmap(char *v)
{
	long long key=0;
	while(*v)
	{
		key=key*4+mctod(*v);
		++v;
	}
	return key;
}

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	int sol=0,p,i=0,j,st,dr,mij;
	char word[32]={0};
	long long k,delta;
	vector <long long>  q;
	fgets(s,LMAX,in);
	n=strlen(s);--n;

	fgets(word,32,in);
	m=strlen(word);--m;
//	printf("%s %s",s,word);
	k=hmap(word);
	q.push_back(k);
	while(fgets(word,32,in)){k=hmap(word);q.push_back(k);}//printf("%s",word);}
	
	k=q[0];p=q.size();
	for(i=1;i<p;++i) if(k>q[i]) k=q[i];
	for(i=0;i<p;++i) q[i]-=k;//printf("%lld ",q[i]);}
	delta=k;
	sort(q.begin(),q.end());


//printf("\n");
	i=0;
	while(i+m<n)
	{
		for(j=0;j<m;++j) word[j]=s[i+j];
		k=hmap(word);
		k-=delta;	
		if(k>=0)
		{
		//	printf("%lld ",k);
			st=0;dr=p-1;
			while(st<=dr)
			{
				mij=(st+dr)/2;
				if(q[mij]==k) break;
				if(q[mij]>k) dr=mij-1;
				else st=mij+1;
			}

			if(k==q[mij]) ++sol;
		}

		++i;
	}

/*	long long alfa=0;
	for(i=1;i<23;++i)
	{
		alfa=alfa*4+3;
		printf("%lld\n",alfa);
	}*/
	fprintf(out,"%d",sol);
	fclose(in);fclose(out);
	return 0;
}