Cod sursa(job #189329)

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

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;

	/* printf("%s\n", A); */
 	int i;
	/* for (i = 0; i < lb; ++i)
		printf("%c ", B[i]);
		printf("\n"); */

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

	/* for (i = 0; i < 26; ++i)
		printf("%c ", 'A'+i);
	printf("\n");
	for (i = 0; i < 26; ++i)
		printf("%d ", next[i]);
		printf("\n"); */

	i = la - 1;
	while (i < lb) {
		/* printf("%d %c\n", i, B[i]); */
		int j = 0;
		while ((j < la) && (A[la-j-1] == B[i-j]))
			++j;

		/* printf("j: %d\n", j); */
		if (j == la) {
			if (N < 1000)
				pos[N++] = i-la+1;
			else
				++N;
		}
		/* printf("Match at %d.\n", i-la+1); */

		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;
}