Pagini recente » Cod sursa (job #2497397) | Cod sursa (job #1664554) | Cod sursa (job #1983898) | Cod sursa (job #1294835) | Cod sursa (job #104592)
Cod sursa(job #104592)
#include<stdio.h>
#include<string.h>
#define N 1000000
char d[N],s[21],a[50001][21];
int n,nr,urm[N],lg,l,use[N];
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])
{
if(!use[j-l+1])
{
nr++;
use[j-l+1]=1;
}
//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;
}