Cod sursa(job #416460)

Utilizator nandoLicker Nandor nando Data 12 martie 2010 20:03:24
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>

#define MAX 2000005

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

void make_prefix(){
	int i,q=0;
	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;
	} 	
}

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

	fgets(A, MAX, fin);
	fgets(B, MAX, fin);
	m=n=0;
	while(('A'<=A[m]&&A[m]<='Z')||('a'<=A[m]&&A[m]<='z')||('0'<=A[m]&&A[m]<='9')){
		m++;
	}
	while(('A'<=B[n]&&B[n]<='Z')||('a'<=B[n]&&B[n]<='z')||('0'<=B[n]&&B[n]<='9')){
		n++;
	}
	i=m;
	while(i){
		A[i]=A[i-1],i--;
	}
	i=n;
	while(i){
		B[i]=B[i-1],i--;
	}
	A[0]=B[0]='\0';
	make_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];
			if (np<1000){
				pos[np]=i-m;
			}
			np++;
		}	
	}		

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