Cod sursa(job #1022417)

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

using namespace std;

int *pi, *match;
string word, text;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

void solve(){
	match = new int[text.size()];
	pi	  = new int[word.size()];
	pi[0] = -1;
	int q = pi[0], 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]){
			match[i] = ++q;
			if (q != 0)
				pi[q] = pi[q-1] + 1;
		} else {
			match[i] = q;
		}
	}

}

void print(){
	int length = word.size() - 1;
	int count = 0;
	for (int i = 0; i < text.size(); i++){
		if (match[i] == length)
			count++;
	}

	g << count << '\n';

	for (int i = 0; i < text.size(); i++){
		cout << match[i] << " ";
		if (match[i] == length)
			g << i - match[i] << " ";
	}
}

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

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