Cod sursa(job #1739493)

Utilizator AplayLazar Laurentiu Aplay Data 9 august 2016 16:02:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

#define MAXN 2000010
#define pb push_back

using namespace std;

char A[MAXN], B[MAXN];
int n, m, F[MAXN], ans;
vector<int> matches;

void failFunction(char* S, int length) {
	int j;

	F[0] = F[1];

	for (int i = 2; i <= length; ++i) {
		j = F[i - 1];

		for ( ; ; ) {
			if (S[j] == S[i - 1]) {
				F[i] = j + 1;
				break;
			}

			if (j == 0) {
				F[i] = 0;
				break;
			}

			j = F[j];
		}
	}
}

void kmp(char* A, int m, char* B, int n, int* F) {
	int i = 0, j = 0;

	while(1) {
		if (j == n) break;

		if (A[i] == B[j]) {
			++i;
			++j;
			if (i == m) {
				++ans;
				if (ans <= 1000)
                    matches.pb(j - m);

			}
		}
		else {
			if (i == 0) {
				++j;
			}
			else {
				i = F[i];
			}
		}
	}
}

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

	scanf("%s\n%s", A, B);

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

	if (m > n) printf("0");
	else {
		failFunction(A, m);
		kmp(A, m, B, n, F);
		printf("%d\n", ans);
		for (int i = 0; i < matches.size(); ++i)
			printf("%d ", matches[i]);
	}

	return 0;
}