Cod sursa(job #1022430)

Utilizator danny794Dan Danaila danny794 Data 5 noiembrie 2013 13:38:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int *pi, rez[1000], count;
string word, text;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

void compute_pi_function(string word) {
	int length = word.size();
	pi = new int[length];
	pi[0] = -1;
	for (int i = 1; i < length; i++){
		int q = pi[i-1];
		while (q != -1 && word[i] != word[q+1])
			q = pi[q];
		if (word[i] == word[q+1])
		 ++q;

		pi[i] = q;
	}
}

void solve(){
	int q = -1, length = word.size();
	for (int i = 0; i < text.size(); i++){
		while (q != -1 && text[i] != word[q+1])
			q = pi[q];
		if (text[i] == word[q+1])
			++q;
		if (q == length - 1){
			if (count <= 1000)
				rez[count] = i - q;
			count++;
		}
	}
}

void print(){
	g << count << "\n";
	int min = count > 1000 ? 1000 : count;
	for(int i = 0; i < min; i++)
		g << rez[i] << " ";
}

void read(){
	f >> word;
	f >> text;
}

int main() {
	read();
	compute_pi_function(word);
	solve();
	print();
	delete [] pi;
	return 0;
}