Cod sursa(job #978344)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 28 iulie 2013 17:45:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<stdio.h>
#include<cstring>
#define NMAX 2000005
#define dimMAX 1000

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

void KMP_prefix(char A[NMAX]){
	int k = 0, i, N = strlen(A)-1;
	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 i, t = 0, M = strlen(B)-1, N = strlen(A)-1;

	for(i = 0; i < M; i++){
		while(t > 0 && A[t] != B[i])
			t = pi[t-1];
		
		if(A[t] == B[i])
			t++;

		if(t == N){
			t = pi[t-1];	
			if(dim < 1000){
				sol[dim] = i - N + 1;
			}
			dim++;
		}

	}
}

int main(){
	FILE *pf, *pg;
	pf = fopen("strmatch.in", "r");
	pg = fopen("strmatch.out", "w");
	
	fgets(A, sizeof(A), pf);
	fgets(B, sizeof(B), pf);

	KMP_prefix(A);
	KMP_match(A, B);
	
	int i;

	fprintf(pg, "%d\n", dim);
	for(i = 0; i < dim && i < 1000; i++)
		fprintf(pg, "%d ", sol[i]);

	fclose(pf);
	fclose(pg);

	return 0;
}