Cod sursa(job #251563)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 2 februarie 2009 22:29:49
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
#include<string.h>

#define NN 2000002
int pi[NN], n, m, s[NN];
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;
}