Cod sursa(job #100574)

Utilizator a7893Nae Mihai a7893 Data 12 noiembrie 2007 13:57:42
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.99 kb
#include<stdio.h>
#include<string.h>
#define N 1000
char d[N*N*10],s[N],a[50000][20];
int n,nr,urm[N],lg,l;
int gasit(char s[])
{
	int i;
	for(i=0;i<n;i++)
		if(strcmp(a[i],s)==0)
			return 1;
	return 0;
}
void read()
{
	scanf("%s",&d);
	while(scanf("%s",&s)!=EOF)
		if(!gasit(s))
			strcpy(a[n++],s);
	lg=strlen(d);
	l=strlen(s);
}
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;
}