Cod sursa(job #396327)

Utilizator allynaAlina S allyna Data 14 februarie 2010 22:48:15
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 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;
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;
}
int main()
{
	unsigned int q=0;
	char a[32];
	int i;
	long int x;
    freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	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;
	for(i=1;i<=lung;i++)
		q=q*3+s[i]-'a';
	if(caut(q))
		++nr;
	for(;s[i] && s[i]!='\n';i++)
	{
		q-=mod*(s[i-lung]-'a');
		q=q*3+s[i]-'a';
		if(caut(q))
			++nr;
	}
	printf("%d\n",nr);
	return 0;
}