Cod sursa(job #410606)

Utilizator nandoLicker Nandor nando Data 4 martie 2010 15:06:03
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>

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

void makePrefix(){
	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(){
	FILE* fin=fopen("strmatch.in","r");
	FILE* fout=fopen("strmatch.out","w");
	fgets(A,MAX,fin);
	fgets(B,MAX,fin);
	int q=0,i;
	while((A[m]>= 'A'&&A[m]<='Z')||(A[m]>='a'&&A[m]<='z')||(A[m]>='0'&&A[m]<='9')){
		m++;
	}
	while((B[n]>= 'A'&&B[n]<='Z')||(B[n]>='a'&&B[n]<='z')||(B[n]>='0'&&B[n]<='9')){
		n++;
	}
	i=m+1;
	while(i--)A[i]=A[i-1];
	i=n+1;
	while(i--)B[i]=B[i-1];
	A[0]=B[0]=' ';
	makePrefix();
	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];
			pos[np++]=i-m;
		}
	}
	fprintf(fout,"%u\n",np);
	np=(np>1000)?1000:np;
	for(i=0;i<np;i++){
		fprintf(fout,"%u ",pos[i]);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}