Cod sursa(job #818708)

Utilizator dariusdariusMarian Darius dariusdarius Data 17 noiembrie 2012 20:49:43
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define DL 10000005
#define DN 30
#define DB 50005
using namespace std;
char s[DL],cuv[DN];
int n,m,nrc,stp;
unsigned int v[DB];
int cb(unsigned int cuv)
{
	int step,p=1;
	for (step=stp;step;step>>=1)
		if (p+step<=nrc && v[p+step]<=cuv) p+=step;
	return v[p]==cuv;
}
int main()
{
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);
	gets(s);int i;
	n=strlen(s)-1;
	while(gets(cuv))
	{
		m=strlen(cuv)-1;
		unsigned int cod=0;
		for(int i=0; i<m; ++i)
			cod=cod*3+cuv[i]-'a';
		v[++nrc]=cod;
	}
	sort(v+1, v+nrc+1);
	unsigned int cod=0,pow=1,sol=0;
	for(i=1;i<m;i++)
        pow*=3;
    for(stp=1;2*stp<nrc;stp<<=1);
	for(i=0;i<m;i++)
		cod=cod*3+s[i]-'a';
    sol+=cb(cod);
	for(i=m;i<n;i++)
	{
		cod-=pow*(s[i-m]-'a');
		cod=cod*3+s[i]-'a';
        sol+=cb(cod);
	}
	printf("%d\n",sol);
	return 0;
}