Pagini recente » Cod sursa (job #2626292) | Cod sursa (job #1577757) | Cod sursa (job #1757936) | Cod sursa (job #2036123) | Cod sursa (job #508005)
Cod sursa(job #508005)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int max=2000001;
char p[max],s[max];
int i,n,m,nr,sol[1001];
int l[max];
void prefix() {
int k,i;
l[1]=0;
for (i=2; i<=m; i++) {
k=l[i-1];
while (k>0 && p[i]!=p[k+1])
k=l[k];
if (p[k+1]==p[i]) k++;
l[i]=k;
}
}
void kmp() {
int k,t;
k=0;
nr=0;
for (t=1; t<=n; t++) {
while (k>0 && p[k+1]!=s[t])
k=l[k];
if (p[k+1]==s[t]) k++;
if (k==m) {
nr++;
if (nr<=1000) sol[nr]=t-m;
k=l[m];
}
}
}
int main () {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(p+1,max,stdin);
fgets(s+1,max,stdin);
nr=0;
n=strlen(s+1)-1;
m=strlen(p+1)-1;
prefix();
kmp();
printf("%d\n",nr);
if (nr>1000) nr=1000;
printf("%d",sol[1]);
for (i=2; i<=nr; i++)
printf(" %d",sol[i]);
printf("\n");
return 0;
}