Cod sursa(job #143902)

Utilizator coderninuHasna Robert coderninu Data 26 februarie 2008 22:21:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
#include <string.h>
#define Nmax 2000005
#define min(a, b) ((a < b) ? a : b)  

char P[Nmax], S[Nmax];
int c[1024], pi[Nmax], i, j, n, m, nr;

int main()
{
	freopen("strmatch.in", "r", stdin);
	scanf("%s\n%s", &P, &S);
	fclose(stdin);

	for (i=0, pi[0]=-1, j=-1, m=strlen(P); i<m; i++, pi[i]=++j)
		while (j>=0 && P[i]!=P[j])
			j=pi[j];
	for (i=0, j=0, n=strlen(S); i<=n; i++)
	{
		while (P[j] !=S[i] && j) j=pi[j];
		if (P[j]==S[i]) j++;
		if (j==m) 
		{
			//if (nr<1000) c[++nr]=i-m+1;
			//if (nr==1000) break;
			j=pi[j];
 			++nr;  
             		if (nr <= 1000)  
                 	c[nr] = i-m+1;
		}
	}
	freopen("strmatch.out", "w", stdout);
	printf("%d\n", nr);  
     	for (i=1; i<=min(nr, 1000); ++i)  
         	printf("%d ", c[i]);  
     printf("\n"); 
	fclose(stdout);
        return 0;
}