Cod sursa(job #1764025)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 24 septembrie 2016 21:53:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#include <string.h>
using namespace std;

int pi[2000010], poz[2000010], i, k, q, n, m, p;
char A[2000010], B[2000010];


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

	scanf("%s", A + 1);
	scanf("%s", B + 1);

	n = strlen(A + 1);
	m = strlen(B + 1);

	for (i = 2; i <= n; i++) {
		while (k > 0 && A[k + 1] != A[i]) {
			k = pi[k];
		}
	
		if (A[k + 1] == A[i]) {
			k++;
		}

		pi[i] = k;
	}

	for (i = 1; i <= m; i++) {
		while (q > 0 && A[q + 1] != B[i]) {
			q = pi[q];
		}

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

		if (q == n) {
			poz[++p] = i - n;
		}
	}


	printf("%d\n", p);
	for (i = 1; i <= p && i <= 1000; i++) {
		printf("%d ", poz[i]);
	}

	return 0;
}