Cod sursa(job #689998)

Utilizator gener.omerGener Omer gener.omer Data 25 februarie 2012 00:57:10
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <string.h>

#define NMAX 2000005

char T[NMAX], P[NMAX];
int b[NMAX];
int pos[1000];

void citire(){
	FILE * f = fopen("strmatch.in", "rt");
	//fscanf(f, "%s %s", P, T);
	fgets(P, NMAX, f);
	P[strlen(P) - 1] = 0;
	fgets(T, NMAX, f);
	T[strlen(T) - 1] = 0;
	fclose(f);
}

void compute_prefix(){
	b[0] = -1;
	int k = -1, i;
	for(i = 0; i < strlen(P);){
		while(k >= 0 && P[i] != P[k])
			k = b[k];
		++k, ++i;
		b[i] = k;
	}
}

int nr_apar = 0;

void scrie_sol(){
	FILE* f = fopen("strmatch.out", "wt");
	int i;
	fprintf(f, "%d\n", nr_apar);
	for(i = 0; i < nr_apar; ++i)
		fprintf(f, "%d ", pos[i]);
	fclose(f);
}

int main(){
	citire();
	compute_prefix();
	int j = 0, i;
	
	for(i = 0; i < strlen(T);){
		while(j >= 0 && P[j] != T[i])
			j = b[j];
		++j, ++i;
		if(j == strlen(P)){
			pos[nr_apar] = i - strlen(P);
			nr_apar++;
			if(nr_apar == 1000)
				break;
			j = b[j];
		}
	}
	
	scrie_sol();
	
	return 0;
}