Pagini recente » Statistici Guta Maria (mariaa.guta12) | Cod sursa (job #2275219) | Cod sursa (job #496009) | Cod sursa (job #732487) | Cod sursa (job #507952)
Cod sursa(job #507952)
#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,q;
l[1]=0;
for (q=2; q<=m; q++) {
k=l[q-1];
while (k>0 && p[k+1]!=p[q])
k=l[k];
if (p[k+1]==p[q])
k=k+1;
l[q]=k;
}
}
void kmp() {
int k,t;
k=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=k+1;
if (k==m) {
nr++;
sol[nr]=t-m;
k=l[k];
}
}
}
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;
}