Cod sursa(job #2215255)

Utilizator bcrsqCont Sters bcrsq Data 21 iunie 2018 14:44:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <cstring>
#include <algorithm>

using namespace std;

#define NMAX 2000000

char P[NMAX + 1], T[NMAX + 1];
int pi[NMAX + 1], pos[1001];
int m, n, counter = 0;

void compute_prefix_function();
void kmp_match();

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	scanf("%s", P);
	scanf("%s", T);

	m = strlen(P);
	n = strlen(T);

	compute_prefix_function();
	kmp_match();

	printf("%d\n", counter);

	for (int i = 1; i <= min(counter, 1000); i++) {
		printf("%d ", pos[i]);
	}

	printf("\n");

	return 0;
}

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

	for (int q = 1; q < m; q++) {
		while (k > -1 && P[k + 1] != P[q]) {
			k = pi[k];
		}

		if (P[k + 1] == P[q]) {
			k++;
		}

		pi[q] = k;
	}
}

void kmp_match() {
	int q = -1;

	for (int i = 0; i < n; i++) {
		while (q > -1 && P[q + 1] != T[i]) {
			q = pi[q];
		}

		if (P[q + 1] == T[i]) {
			q++;
		}

		if (q == m - 1) {
			counter++;

			if (counter <= 1000) {
				pos[counter] = i - m + 1;
			}

			q = pi[q];
		}
	}
}