Cod sursa(job #416441)

Utilizator nandoLicker Nandor nando Data 12 martie 2010 19:39:25
Problema Potrivirea sirurilor Scor 32
Compilator c Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>

#define MAX 2000005

char A[MAX],B[MAX];
int pi[MAX],pos[1024],m,n,np=0;

int main(void)
{
	int i, q = 0, n = 0;
	FILE* fin=fopen("strmatch.in","r");
	FILE* fout=fopen("strmatch.out","w");

	fgets(A+1, MAX, fin);
	fgets(B+1, MAX, fin);
	A[0]=B[0]=' ';
	m=strlen(A),n=strlen(B);
	A[--m]='\0',B[--n]='\0',m--,n--;

	pi[1]=0;

	for (i=2;i<=m;i++){
		while(q&&A[q+1]!=A[i]){
			q = pi[q];
		}
		if (A[q+1] == A[i]){
			q++;
		}
		pi[i]=q;
	} 	
	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];
			if (np<1000)
				pos[np++]=i-m;	
		}	
	}		

	fprintf(fout,"%d\n", np);
	for (i=0;i<((np<1000)?np:1000);i++){
		fprintf(fout,"%d ",pos[i]);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}