Pagini recente » Cod sursa (job #870464) | Cod sursa (job #1090268) | Cod sursa (job #1607590) | Cod sursa (job #81128) | Cod sursa (job #251567)
Cod sursa(job #251567)
#include<stdio.h>
#include<string.h>
#define NN 200002
int pi[NN], n, m, s[1002];
char a[NN], b[NN];
void prefix(){
int i, q = 0;
for (i = 2; i <= n; i++){
while ((q>0) && a[q+1] != a[i]) q = pi[q];
if (a[q+1] == a[i]) q++;
pi[i] = q;
}
}
int main(){
int i, q = 0, nr = 0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s", a+1); n = strlen(a+1);
scanf("%s", b+1); m = strlen(b+1);
prefix();
for (i = 1, q = 0; i <= m; i++){
while ((q>0) && a[q+1] != b[i]) q = pi[q];
if (a[q+1] == b[i]) q++;
if (q == n){
++nr;
if (nr <= 1000) s[nr] = i-n;
}
}
printf("%d\n", nr);
if (nr > 1000) nr = 1000;
for (i = 1; i <= nr; i++) printf("%d ", s[i]);
printf("\n");
return 0;
}