Pagini recente » Cod sursa (job #2293078) | Cod sursa (job #703518) | Cod sursa (job #1131349) | Cod sursa (job #705772) | Cod sursa (job #156307)
Cod sursa(job #156307)
# include <stdio.h>
# include <string.h>
# define nmax 2000002
# define FIN "strmatch.in"
# define FOUT "strmatch.out"
char T[nmax],P[nmax];
int x,k,i,n,m,Next[nmax],ct,sol[1001];
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%s",P+1); scanf("%s",T+1);
m=strlen(P+1); n=strlen(T+1);
Next[1]=0; k=0;
for (i=2; i<=m; i++)
{
while (k>0 && P[k+1]!=P[i]) k=Next[k];
if (P[k+1]==P[i]) k++;
Next[i]=k;
}
x=0; ct=0;
for (i=1; i<=n; i++)
{
while (x>0 && P[x+1]!=T[i]) x=Next[x];
if (P[x+1]==T[i]) x++;
if (x==m)
{
ct++;
if (ct<=1000) sol[ct]=i-m;
x=Next[x];
}
}
printf("%ld\n",ct);
if (ct>1000) ct=1000;
for (i=1; i<=ct; i++)
printf("%ld ",sol[i]);
return 0;
}