Cod sursa(job #605955)

Utilizator bogdanacmDrutu Bogdan bogdanacm Data 2 august 2011 23:39:47
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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, MAXN, stdin);
	N = strlen(a) - 1;
	a[N] = '\0';
	fgets(b, MAXN, stdin);
	M = strlen(b) - 1;
	b[N] = '\0';

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

	return 0;
}