Cod sursa(job #1072609)

Utilizator danny794Dan Danaila danny794 Data 4 ianuarie 2014 17:48:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <string>

#define MAXN 2000003

using namespace std;

char word[MAXN], text[MAXN];
int fi_word[MAXN], fi_text[MAXN], result[1002], count = 0;

void read() {
	freopen( "strmatch.in", "r", stdin );
	freopen( "strmatch.out", "w", stdout );
	scanf("%s", word);
	scanf("%s", text);
}

int getLength(char *c) {
	int len = 0;
	while( *c != '\0') {
		c++;
		len++;
	}
	return len;
}

void compute_word() {
	fi_word[0] = -1;
	int length = getLength(word);
	int q;
	for(int k = 1; k < length; k++) {
		q = fi_word[k-1];
		while( q != -1 && word[k] != word[q + 1] )
			q = fi_word[q];
		if( word[k] == word[q + 1] )
			q++;
		fi_word[k] = q;
	}
}

void solve() {
	int length_text = getLength(text);
	int length_word = getLength(word);
	int k = -1;
	for(int i = 0; i < length_text; i++) {

		while( k != -1 && text[i] != word[k + 1])
			k = fi_word[k];

		if( text[i] == word[k+1] )
			k++;

		if ( k == length_word - 1) {
			count++;
			if (count < 1001)
				result[count] = i + 1 - length_word;
		}
	}
}

void print() {

	printf("%i\n", count);
	int min = count < 1001 ? count : 1000;
	for(int i = 1; i <= min; i++)
		printf("%i ", result[i]);
}

int main() {
	read();
	compute_word();
	solve();
	print();
	return 0;
}