Cod sursa(job #342185)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 20 august 2009 19:03:10
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int m=1<<19;
int n,nr,lung,mod;
char s[1<<24];
vector <unsigned int> v;

void read()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	char a[32];
	int i;
	long int x;
	gets(s+1);
	n=strlen(s+1);
	fgets(a,32,stdin);
	lung=strlen(a)-1;
	x=0;
	for(i=0;i<lung;i++)
		x=x*3+a[i]-'a';
	v.push_back(x);
	while(fgets(a,32,stdin))
	{
		x=0;
		for(i=0;i<lung;i++)
			x=x*3+a[i]-'a';
		v.push_back(x);
	}
	sort(v.begin(),v.end());
	mod=1;
	for(i=1;i<lung;i++)
		mod=mod*3;
}

bool caut(int x)
{
	int i,pas,n=v.size();
	for(pas=1;pas<=n;pas<<=1);
	for(i=0;pas;pas>>=1)
		if(i+pas<n && v[i+pas]<=x)
			i+=pas;
	return v[i]==x;
}

void rez()
{
	unsigned int x=0;
	int i;
	for(i=1;i<=lung;i++)
		x=x*3+s[i]-'a';
	if(caut(x))
		++nr;
	for(;s[i] && s[i]!='\n';i++)
	{
		x-=mod*(s[i-lung]-'a');
		x=x+x+x+s[i]-'a';
		if(caut(x))
			++nr;
	}
	printf("%d\n",nr);
}

int main()
{
	read();
	rez();
	return 0;
}