Cod sursa(job #605961)

Utilizator bogdanacmDrutu Bogdan bogdanacm Data 2 august 2011 23:47:47
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
//============================================================================
// Name        : KMP.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

using namespace std;

#define MAXN 2000010
#define pb push_back

char a[MAXN], b[MAXN];
int N,M;
int pi[MAXN];
vector<int> solve;

void make_prefix() {
	int k = -1, i;
	for (i = 1, pi[0] = -1; i < N; i++) {
		while (k >= 0 && a[k + 1] != a[i])
			k = pi[k];

		if (a[k + 1] == a[i])
			k++;

		pi[i] = k;
	}
}

void KMP() {
	int k = -1, i;

	for (i = 0; i < M; i++) {
		while (k >= 0 && a[k + 1] != b[i])
			k = pi[k];

		if (a[k + 1] == b[i])
			k++;

		if (k == N - 1)
			solve.pb(i - N + 1);
	}
}
int main() {

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

	fgets(a, sizeof(b), stdin);
	fgets(a, sizeof(b), stdin);
	for (; (a[N] >= 'A' && a[N] <= 'Z') || (a[N] >= 'a' && a[N] <= 'z') || (a[N] >= '0' && a[N] <= '9'); ++N);
	for (; (b[M] >= 'A' && b[M] <= 'Z') || (b[M] >= 'a' && b[M] <= 'z') || (b[M] >= '0' && b[M] <= '9'); ++M);

	make_prefix();
	KMP();
	printf("%d\n", solve.size());
	for (unsigned i = 0 ; i < solve.size() && i < 1000; i++)
		printf("%d ", solve[i]);

	return 0;
}