Cod sursa(job #808636)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 7 noiembrie 2012 01:05:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int p, t;
int size;
int ans[2000002];
char P[2000002], T[2000002];

vector<int> pre_kmp(char P[], int p) {
	vector<int> b(p + 1, 1 << 30);
	int i = 0, j = -1;
	b[i] = j;
	while (i < p) {
		while (!(j == -1 || P[i] == P[j])) {
			j = b[j];
		}
		i++;
		j++;
		b[i] = j;
	}
	return b;
}

void kmp(char P[], int p, char T[], int t) {
	vector<int> b = pre_kmp(P, p);
	int i = 0, j = 0;
	while (i < t) {
		while (!(j == -1 || T[i] == P[j])) {
			j = b[j];
		}
		i++;
		j++;
		if (j == p) {
			ans[size++] = i - j;
			j = b[j];
		}
	}
}

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