Cod sursa(job #1022397)

Utilizator danny794Dan Danaila danny794 Data 5 noiembrie 2013 12:55:50
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

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

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

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