Cod sursa(job #1882421)

Utilizator cautionPopescu Teodor caution Data 17 februarie 2017 10:40:09
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 20000000;
const int kMaxPrint = 1000;

int len_A;
char A[kMaxN + 2], B[kMaxN + 2];
int prefix[kMaxN + 2];
vector<int> matches;

void compute_prefix()
{
	prefix[1] = 0;
	int k = 0;
	for (int i = 2; A[i] != '\0'; ++i) {
		while (k > 0 && A[k + 1] != A[i]) k = prefix[k];
		if (A[k + 1] == A[i]) ++k;
		prefix[i] = k;
	}
}

void kmp()
{
	int k = 0;
	for (int i = 1; B[i] != '\0'; ++i) {
		while (k > 0 && A[k + 1] != B[i]) k = prefix[k];
		if (A[k + 1] == B[i]) ++k;
		if (A[k + 1] == '\0') {
			matches.push_back(i - len_A + 1);
			k = prefix[k];
			if (matches.size() == kMaxPrint) return;
		}
	}
}

int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);

	scanf("%s", A);
	scanf("%*c");
	scanf("%s", B);
	len_A = strlen(A);
	compute_prefix();
	kmp();

	printf("%lu\n", matches.size());
	for (auto x : matches) printf("%d ", x);
	printf("\n");

	return 0;
}