Cod sursa(job #407178)

Utilizator johsonsbabiJohnsons Babi Minune johsonsbabi Data 2 martie 2010 09:32:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#define MAXX 2000005
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
char P[MAXX],T[MAXX];
int urm[MAXX],pos[1005];
int p,t,k,q,n;
void citire(){
	do{
		fscanf(f,"%c",&P[++p]);
	}while(P[p]!='\n');
	P[p]=0;
	p--;
	do{
		fscanf(f,"%c",&T[++t]);
		if(feof(f)){
			t--;
			break;
		}
	}while(T[t]!='\n');
	if(T[t]=='\n'){
		T[t]=0;
		t--;
	}
}

void urmatorul(){
	int i;
	for(i=2;i<=p;i++){
		while(k>0 && P[k+1]!=P[i]){
			k=urm[k];
		}
		if(P[k+1]==P[i]){
			k++;
		}
		urm[i]=k;
	}
}

void solve(){
	urmatorul();
	int i;
	k=0;
	for(i=1;i<=t;i++){
		while(k>0 && P[k+1]!=T[i]){
			k=urm[k];
		}
		if(P[k+1]==T[i]){
			k++;
		}
		if(k==p){
			k=urm[k];
			n++;
			if(n<=1000)
				pos[n]=i-p;
		}
	}
}

void afis(){
	int i;
	fprintf(g,"%d\n",n);
	for(i=1;i<=n;i++){
		fprintf(g,"%d ",pos[i]);
	}
	
}

int main(){
	
	citire();
	solve();
	afis();
	
	fclose(f);
	fclose(g);
	return 0;
}