Cod sursa(job #785285)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 8 septembrie 2012 12:53:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cassert>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2000005;

char text[N], pattern[N];
int prefix[N], sol[N];

void read() {
	assert(freopen("strmatch.in", "r", stdin) != NULL);
	assert(freopen("strmatch.out", "w", stdout) != NULL);
	
	assert(scanf("%s", pattern + 1) == 1);
	assert(scanf("%s", text + 1) == 1);
}

void Prefix() {
	int p = 0;
	int n = strlen(pattern + 1);
	
	prefix[1] = 0;
	for (int i = 2; i <= n; ++i) {
		while (p > 0 && pattern[p + 1] != pattern[i])
			p = prefix[p];
		
		if (pattern[p + 1] == pattern[i])
			++p;
		
		prefix[i] = p;
	}
}

void match() {
	int p = 0;
	int n = strlen(text + 1);
	int m = strlen(pattern + 1);
	
	for (int i = 1; i <= n; ++i) {
		while (p > 0 && pattern[p + 1] != text[i])
			p = prefix[p];
		
		if (pattern[p + 1] == text[i])
			++p;
		
		if (p == m) {
			sol[++sol[0]] = i - m;
			p = prefix[p];
		}
	}
}

void write() {
	int n = 1000 < sol[0] ? 1000:sol[0];
	
	printf("%d\n", sol[0]);
	for (int i = 1; i <= n; ++i)
		printf("%d ", sol[i]);
}

int main() {
	read();
	Prefix();
	match();
	write();
}