Cod sursa(job #100599)

Utilizator a7893Nae Mihai a7893 Data 12 noiembrie 2007 14:42:08
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.35 kb
#include<stdio.h>
#include<string.h>
#define N 1000
char d[N],s[N],a[50000][20],use[3][100001];
int n,nr,urm[N],lg,l,ind[100000];
int gasit(char s[])
{
	int i;
	for(i=0;i<n;i++)
		if(strcmp(a[i],s)==0)
			return 1;
	return 0;
}
int poz(int c,int st)
{
	int i;
	for(i=st;i<=l;i++)
		if(use[c][i]!=s[i-st])
			return 0;
	if(i-st!=l)
		return 0;
	return 1;
}
int gasit2(char s[])
{
	int i;
	for(i=1;i<=ind[s[0]-'a'];i+=l)
		if(poz(s[0]-'a',i))
			return 1;
	return 0;
}
void read()
{
	int i;
	scanf("%s",&d);
	while(scanf("%s",&s)!=EOF)
	{
		l=strlen(s);
		if(!gasit2(s))
		{
			strcpy(a[n++],s);
			for(i=0;i<l;i++)
				use[s[0]-'a'][++ind[s[0]-'a']]=s[i];
		}
	}
	lg=strlen(d);
}
void next(char *p)
{
	int k=-1,x;
	urm[0]=0;
	for(x=1;x<l;x++)
	{
		while(k>0&&p[k+1]!=p[x])
			k=urm[k];
		if(p[k+1]==p[x])
			k++;
		urm[x]=k;
	}
}
void solve()
{
	int i,j,x=-1;
	for(i=0;i<n;i++)
	{
		memset(urm,0,sizeof(urm));
		x=-1;
		next(a[i]);
		for(j=0;j<lg;j++)
		{
			while(x>0&&a[i][x+1]!=d[j])
				x=urm[x];
			if(a[i][x+1]==d[j])
				x++;
			if(x==l-1&&a[i][0]==d[j-l+1])
			{
				nr++;
				//printf("am gasit %s pe pozitia: %d\n",a[i],j-l+1);
				x=urm[x];
			}
		}
	}
	printf("%d\n",nr);
}
int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	read();
	solve();
	return 0;
}