Cod sursa(job #100436)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 12 noiembrie 2007 10:48:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.23 kb
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

#define maxx 10000010
#define maxn 50010
#define maxl 25
#define mod 666013
#define pb push_back
#define us unsigned int

int n,m,L,sol;
char a[maxx],u[maxx];
char b[maxn][maxl];
int p[maxn],l[maxn];
vector <us> hash[mod];

int cmp(int x,int y)
{
	return l[x]<l[y];
}

inline int search(us x)
{
	int y=x%mod,i,l=hash[y].size();

	for (i=0;i<l;i++)
		if (x==hash[y][i]) return 1;
	
	return 0;
}

int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);

	scanf("%s ",a+1);
	a[0]=' ';
	n=strlen(a)-1;

	int i,j;
	us x,y;

	while (!feof(stdin))
	{
		m++;
		scanf("%s ",b[m]+1);
		b[m][0]=' ';
		l[m]=strlen(b[m])-1;
		p[m]=m;
	}

	sort(p+1,p+m+1,cmp);

	for (i=1;i<=m && n>=l[p[i]];)
	{
		for (j=0;j<mod;j++) vector <us> ().swap(hash[j]);
			
		for (L=l[p[i]];i<=m && L==l[p[i]];i++)
		{
			x=0;
			for (j=1;j<=L;j++) x=x*3+(b[p[i]][j]-'a');
			hash[x%mod].pb(x);
		}

		x=0,y=1;
		for (j=1;j<=L;j++)
		{
			x=x*3+(a[j]-'a');
			if (j>1) y*=3;
		}
	
		for (j=L+1;j<=n+1;j++)
		{
			if (!u[j-L] && search(x))
			{
				sol++;
				u[j-L]=1;
			}
			x=x-y*(a[j-L]-'a');
			x*=3;
			if (j<n) x+=a[j]-'a';
		}
	}

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

	return 0;
}