Cod sursa(job #189330)

Utilizator scvalexAlexandru Scvortov scvalex Data 13 mai 2008 19:01:23
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <string.h>

/*
 * Acesta este Boyer-Moore,
 * Un algoritm simplut dar pur,
 * Usor scris, e un balaur,
 * Doar ca moare la graurururururu,
 * Si urururururuurururururururururuurururururur.
 */

char A[2000002];
int next[26];
char B[2000002];

int N;
int pos[1000];

int main(int argc, char *argv[])
{
	FILE *fi = fopen("strmatch.in", "r");
	fscanf(fi, "%s\n", A);
	fscanf(fi, "%s\n", B);
	fclose(fi);

	int la = strlen(A);
	int lb = strlen(B);
	if (la > lb)
		goto down;

 	int i;
	for (i = 0; i < 26; ++i)
		next[i] = la;
	for (i = 0; i < la-1; ++i)
		next[A[i]-'A'] = la - i - 1;

	i = la - 1;
	while (i < lb) {
		int j = 0;
		while ((j < la) && (A[la-j-1] == B[i-j]))
			++j;

		if (j == la) {
			if (N < 1000)
				pos[N++] = i-la+1;
			else
				++N;
		}

		i += next[B[i] - 'A'];
	}

down:
	;
	FILE *fo = fopen("strmatch.out", "w");
	fprintf(fo, "%d\n", N);
	for (i = 0; (i < N) && (i < 1000); ++i)
		fprintf(fo, "%d ", pos[i]);
	fprintf(fo, "\n");
	fclose(fo);

	return 0;
}