Cod sursa(job #2470562)

Utilizator ShayTeodor Matei Shay Data 9 octombrie 2019 14:55:24
Problema Potrivirea sirurilor Scor 24
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 1000
#define BUFFER_SIZE 1 << 17

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	char pattern[BUFFER_SIZE], string[BUFFER_SIZE];

	scanf("%s%s", pattern, string);

	int len_pattern = strlen(pattern);
	int len_string = strlen(string) - 1;

	if (len_pattern > len_string) {
		fprintf(stderr, "Gigele, nu-i de bine...\n");
		goto error;
	}

	int i = 1, j = 0, count = 0;
	int *pi = calloc(len_pattern, sizeof(*pi));
	int *position = calloc(NMAX, sizeof(*position));

build_pref_array:
	if (i == len_pattern) {
		goto KMP;
	}

back_pref_array:
	if (j && pattern[i] != pattern[j]) {
		j = pi[j - 1];
		goto back_pref_array;
	}

	if (pattern[i] == pattern[j]) {
		++j;
	}

	pi[i] = j;
	++i;
	goto build_pref_array;
	
KMP:
	i = 0, j = 0;

search:
	if (i == len_string) {
		goto print;
	}

match:
	if (j && pattern[j] != string[i]) {
		j = pi[j - 1];
		goto match;
	}

	if (pattern[j] == string[i]) {
		++j;
	}

	if (j == len_pattern) {
		position[count++] = i - len_pattern + 1;
		j = pi[j - 1];
	}

	++i;
	goto search;

print:
	printf("%d\n", count);
	i = 0;

print_position:
	if (i < count) {
		printf("%d ", position[i]);
		++i;
		goto print_position;
	}

	printf("\n");

error:
	free(pi);
	free(position);
	fclose(stdin);
	return 0;
}