Cod sursa(job #105573)

Utilizator Binary_FireFlorin Pg Binary_Fire Data 17 noiembrie 2007 19:23:22
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.36 kb
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

#define pb push_back
#define sz(c) (int)((c).size())

#define fin  "abc2.in"
#define fout "abc2.out"

const int Nmax = 100;
const int Mmax = 10000010;

int N,ret;
char buff[Nmax];
char txt[Mmax];
vector <unsigned int> v;

void ins(char a[])
{
	int i;
	unsigned int pt,tmp;

	pt=1; tmp=0;

	for (i=0;i<N;++i)
	{
		tmp = tmp + ( a[i] - 'a' ) * pt;
		pt *= 3;
	}

	v.pb(tmp);
}

inline int search(unsigned int val)
{
	int i,step;

	for ( step = 1 ; step < sz(v) ; step <<= 1 );

	for ( i = 0 ; step ; step >>= 1 )
		if ( i + step < sz(v) && v[i+step] <= val )
			i += step;

	if ( v[i] != val ) return -1;

	return i;
}

int main()
{
	int i;
	unsigned int pt,tmp;

	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	fgets(txt,Mmax,stdin);
	fgets(buff,Nmax,stdin);

	for ( i = 0 ; 'a' <= txt[i] && txt[i]<='c' ; ++i )
		txt[i]-='a';

	while ( 'a' <= buff[N] && buff[N] <= 'c' ) ++ N ;

	ins(buff);

	while ( !feof(stdin) ) 
	{
		fgets(buff,Nmax,stdin);
		ins(buff);
	}
	
	sort(v.begin(),v.end());

	tmp=0; pt=1;

	for (i=0;i<N;++i)
	{
		tmp = tmp + txt[i] * pt;
		pt*=3;
	}

	pt/=3;

	if ( search(tmp) != -1 ) ++ret;

	for (i=N; 0 <= txt[i] && txt[i] <= 2 ;++i)
	{
		tmp -= txt[i-N];
		tmp /= 3;
		tmp  = tmp + txt[i]*pt;
		if ( search(tmp) != -1 ) ++ret;
	}

	printf("%d\n",ret);

	return 0;
}