Cod sursa(job #789458)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 18 septembrie 2012 11:43:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cassert>
#include <cstdio>
#include <cstring>

#include <algorithm>
using namespace std;

const int N = 2000005;

int sol[N], d[N], dPrim[N];
char text[N], pattern[N];

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

void zalgorithm() {
	int n = strlen(pattern + 1);
	int best;
	
	d[1] = 0;
	best = 0;
	for (int i = 2; i <= n; ++i) {
		if (best + d[best] >= i)
			d[i] = min(d[i - best + 1], best + d[best] - i);
		
		while (i + d[i] <= n && pattern[d[i] + 1] == pattern[i + d[i]])
			++d[i];
		
		if (i + d[i] > best + d[best])
			best = i;
	}
}

void match() {
	int n = strlen(text + 1);
	int m = strlen(pattern + 1);
	int best;
	
	best = 0;
	for (int i = 1; i <= n; ++i) {
		if (best + dPrim[best] >= i)
			dPrim[i] = min(d[i - best + 1], best + dPrim[best] - i);
		
		while (i + dPrim[i] <= n && dPrim[i] + 1 <= m && pattern[dPrim[i] + 1] == text[i + dPrim[i]])
			++dPrim[i];
		
		if (i + dPrim[i] > best + dPrim[best])
			best = i;
		
		if (dPrim[i] == m)
			sol[++sol[0]] = i;
	}
}

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

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