Cod sursa(job #500407)

Utilizator vlad_DVlad Dumitriu vlad_D Data 12 noiembrie 2010 07:20:19
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <string.h>
#include <cstdio>

using namespace std;
int F[1000];
int M, N;
void build_failure(char pattern[]) {
	//0...M-1
	F[0] = F[1] = 0;
	for (int i = 2; i <= M; ++i) {
		int j = F[i-1];
		while (1) {
			if (pattern[j] == pattern[i-1]) {
				F[i] = j + 1; break;
			}
			if (j == 0) {F[i] = 0; break;}
			j = F[j];
		}
	}
}
int v[200002];
void kmp(char text[], char pattern[]) {
	build_failure(pattern);
	int i = 0, j = 0;
	while (1) {
		if (i == N) break;
		if (text[i] == pattern[j]) {
			++i;++j;
			if (j == M) {
				v[++v[0]] = 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);
	char pattern[2000001];
	char text[2000001];
	scanf("%s %s", &pattern, &text);
	N = strlen(text); M = strlen(pattern);
	kmp(text, pattern);
	printf("%d\n", v[0]);
	for (int i = 1; i <= v[0]; ++i)
		printf("%d ", v[i]);
	return 0;
}