Cod sursa(job #978247)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 28 iulie 2013 14:35:38
Problema Potrivirea sirurilor Scor 6
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000001

int sol[NMAX];
int pi[NMAX];
char A[NMAX], B[NMAX];
int dim = 0;

void read(FILE *pf){
	fscanf(pf, "%s", A);
	fscanf(pf, "%s", B);
	
}

void KMP_prefix(char A[NMAX], int N){
	int k = 0, i;
	pi[k] = 0;
	for(i = 1; i < N; i++){
		while(k > 0 && A[k] != A[i])
			k = pi[k];
		if(A[k] == A[i])
			k++;
		pi[i] = k;
	}
}

void KMP_match(char A[NMAX], char B[NMAX], int N, int M){
	int t = 0, i = 0;

	while(i < M){
		while(t > 0 && A[t] != B[i])
			t = pi[i];
		if(A[t] == B[i])
			t++;
		if(t == N){
			sol[dim] = i - N + 1;
			dim++;
			i = i - N + 2;
		}
		else
			i++;
	}
}

void print(FILE *pg){
	int i;
	fprintf(pg, "%d\n", dim);
	for(i = 0; i < dim; i++)
		fprintf(pg, "%d ", sol[i]);
}

int main(){
	int M, N;
	FILE *pf, *pg;
	pf = fopen("strmatch.in", "r");
	pg = fopen("strmatch.out", "w");

	read(pf);
	N = sizeof(A);
	M = sizeof(B);

	KMP_prefix(A, N);
	KMP_match(A, B, N, M);

	print(pg);
	fclose(pf);
	fclose(pg);

	return 0;
}