Cod sursa(job #251461)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 2 februarie 2009 18:40:01
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>

int pi[100], n, m, a[100];
char A[100], B[100];


void prefix(){
int i, q = 0;

     for (i = 2, pi[1] = 0; i <= m; i++){

	 while (q && 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); m = strlen(A);
    for (i = n; i; --i)  A[i] = A[i-1]; A[0] = ' ';
    scanf("%s", &B); n = strlen(B);
    for (i = m; i; --i)  B[i] = B[i-1]; B[0] = ' ';

    prefix();

    for (i = 1; i <= n; i++){

	while (q && A[q+1] != B[i])
		q = pi[q];

	if (A[q+1] == B[i]) q++;

	if (q == m){

		q = pi[m];
		++nr;
		if (nr <= 1000)
			a[nr] = i-m;

	}
    }

    printf("%d\n", nr);
    if (nr > 1000) nr = 1000;

    for (i = 1; i <= nr; i++)
	printf("%d ", a[i]);
    printf("\n");

    return 0;
}