Cod sursa(job #170795)

Utilizator plastikDan George Filimon plastik Data 3 aprilie 2008 11:19:41
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 2000005;
const int MMAX = 1024;

char Text[NMAX], Word[NMAX];
int Pi[NMAX], lw, lt;

int Match[MMAX], nm = 0;

void KMPFailureFunction() {
	int i, k;
	Pi[1] = 0;
	for (i = 2, k = 0; i <= lw; ++ i) {
		while (k > 0 && Word[i] != Word[k + 1])
			k = Pi[k];
		if (Word[i] == Word[k + 1])
			++ k;
		Pi[i] = k;
	}
}

void KMPSearch() {
	int i, k;
	for (i = 1, k = 0; i <= lt; ++ i) {
		while (k > 0 && Text[i] != Word[k + 1])
			k = Pi[k];
		if (Text[i] == Word[k + 1])
			++ k;
		
		if (k == lw) {
			if (nm < 1000)
				Match[nm] = i - lw;
			++ nm;
			k = Pi[k];
		}
	}	
}

int main() {
	
	freopen("kmp.in", "r", stdin);
	freopen("kmp.out", "w", stdout);
	
	scanf("%s", Word + 1);
	scanf("%s", Text + 1);
	lw = strlen(Word + 1), lt = strlen(Text + 1);
	
	KMPFailureFunction();
	KMPSearch();
	
	printf("%d\n", nm);
	int i;
	for (i = 0; i < min(nm, 1001); ++ i)
		printf("%d ", Match[i]);
	
	return 0;
}