Cod sursa(job #638664)

Utilizator Mach3Pavaluca Matei Mach3 Data 21 noiembrie 2011 12:39:29
Problema Potrivirea sirurilor Scor 14
Compilator c Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <string.h>

#define maxlen 2000002
//#define MIN(A, B) ((A) < (B)) ? (A) : (B)

char A[maxlen], B[maxlen], m, n;
int pi[maxlen];

void prefix() {
	int k = 0;
	pi[1] = 0;

	int i;
	for (i = 2; i <= m; i++) {
		while (k && A[k + 1] != A[i])
			k = pi[k];

		if (A[k + 1] == A[i])
			k = k + 1;

		pi[i] = k;
	}

	for (i = 0; i <= m; i++)
		printf("%d ", pi[i]);
}


int main() {

	FILE *in = fopen("strmatch.in", "r");

	fgets(A, maxlen, in);
	fgets(B, maxlen, in);

	fclose(in);

	m = strlen(A);
	n = strlen(B);
	m--;
	n--;

	int i;
	for (i = m; i > 0; i--)
		A[i] = A[i - 1];
	A[0] = ' ';

	for (i = n; i > 0; i--)
		B[i] = B[i - 1];
	B[0] = ' ';

	prefix();

	int q = 0, j = 0, ans[1000];
	
	for (i = 0; i < n; i++) {
		while (q && A[q + 1] != B[i])
			q = pi[q];

		if (A[q + 1] == B[i])
			q++;

		if (q == m) {
			q = pi[m];
			j++;
			if (j < 1000)
				ans[j - 1] = i - m;
		}
	}
	
	FILE *out = fopen("strmatch.out", "w");
	fprintf(out, "%d\n", j); 
	
	int min = (j < 1000) ? j : 1000;
	
	for (i = 0; i < min; i++)
		fprintf(out, "%d ", ans[i]);

	fclose(out);

	return 0;
}