Pagini recente » Cod sursa (job #781773) | Cod sursa (job #885102) | Cod sursa (job #1006139) | Cod sursa (job #1204804) | Cod sursa (job #508224)
Cod sursa(job #508224)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max 2000002
char p[max],t[max];
int n,m,i,k,nr,l[max],sol[1001];
int main () {
freopen("grader_test50.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(p+1,max,stdin);
fgets(t+1,max,stdin);
n=strlen(p+1)-1;
m=strlen(t+1)-1;
l[1]=0;
for (i=2; i<=n; i++) {
k=l[i-1];
while (k>0 && p[i]!=p[k+1]) k=l[k];
if (p[i]==p[k+1]) k++;
l[i]=k;
}
k=0;
nr=0;
for (i=1; i<=m; i++) {
while (k>0 && t[i]!=p[k+1]) k=l[k];
if (t[i]==p[k+1]) k++;
if (k==n) {
nr++;
if (nr<=1000) sol[nr]=i-n;
k=l[n];
}
}
printf("%d\n",nr);
if (nr>1000) nr=1000;
for (i=1; i<=nr; i++) printf("%d ",sol[i]);
printf("\n");
return 0;
}