Cod sursa(job #1423679)

Utilizator phobosJustin Lim Kai Ze phobos Data 22 aprilie 2015 11:38:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MX = 2*1e6+1;
int n, m, F[MX];
char S[MX], P[MX];
vector<int> pos;

void build() {
	F[0] = 0, F[1] = 0;
	for (int i = 2; i <= m; i++) {
		int j = F[i-1];
		while (1) {
			if (P[j] == P[i-1]) {
				F[i] = j+1;
				break;
			}
			else if (j > 0) {
				j = F[j];
			}
			else {
				F[i] = 0;
				break;
			}
		}
	}
}

void kmp() {
	int i = 0, j = 0;
	while (1) {
		if (i == n) break;
		if (P[j] == S[i]) {
			i++, j++;
			if (j == m) {
				pos.push_back(i-m);
				j = F[j];
			}
		}
		else if (j > 0) {
			j = F[j];
		}
		else {
			i++;
		}
	}
}

int main() {
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	scanf("%s%s", &P, &S);
	n = strlen(S), m = strlen(P);
	build();
	kmp();
	int sz = pos.size();
	printf("%d\n", sz);
	for (int i = 0; i < min(sz, 1000); i++) {
		printf("%d ", pos[i]);
	}
	return 0;
}