Cod sursa(job #1306976)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 31 decembrie 2014 19:02:44
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <string.h>
#define NMAX 2000000
#define BMAX 1000

char A[NMAX + 2], B[NMAX + 2];
int pi[NMAX + 2], buff[BMAX + 1], sp;
int M, N;

void preproc()
{
	int k = 0, q;
	for (q = 1; q < M; q++) {
		while ((k > 0) && (A[k] != A[q])) {
			k = pi[k - 1];
		}
		if (A[k] == A[q]) {
			k++;
		}
		pi[q] = k;
	}
}

void KMP()
{
	int q = 0, i;
	for (i = 0; i < N; i++) {
		while ((q > 0) && (A[q] != B[i])) {
			q = pi[q - 1];
		}
		if (A[q] == B[i]) {
			q++;
		}
		if (q == M) {
			sp++;
			if (sp <= BMAX) {
				buff[sp] = i - M + 1;
			}
		}
	}
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("strmatch.in", "r");
	fout = fopen("strmatch.out", "w");

	fgets(A, sizeof(A), fin);
	fgets(B, sizeof(B), fin);
	M = strlen(A) - 1;
	N = strlen(B) - 1;
	
	preproc();
	KMP();
	fprintf(fout, "%d\n", sp);
	int i;
	for (i = 1; i <= sp && i <= BMAX; i++) {
		fprintf(fout, "%d ", buff[i]);
	}
	fprintf(fout, "\n");

	fclose(fin);
	fclose(fout);
	return 0;
}