Cod sursa(job #1830833)

Utilizator k.bruenDan Cojocaru k.bruen Data 17 decembrie 2016 10:45:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <string>
#include <vector>
using std::ifstream;
using std::ofstream;
using std::string;
using std::vector;

string input, substr;

vector<int> KMP(string input, string substr) {
	vector<int> positions(substr.size() + 1, -1);
	vector<int> result;

	for (unsigned int i = 1; i <= substr.size(); i++) {
		int pos = positions.at(i - 1);
		while (pos != -1 && substr[pos] != substr[i - 1]) pos = positions.at(pos);
		positions.at(i) = pos + 1;
	}

	int pos_input = 0, pos_substr = 0;
	while (pos_input < input.size()) {
		while (pos_substr != -1 && (substr[pos_substr] != input[pos_input] || pos_substr == substr.size())) pos_substr = positions.at(pos_substr);
		pos_substr++;
		pos_input++;
		if (pos_substr == substr.size()) result.push_back(pos_input - pos_substr);
	}

	return result;
}

ifstream in("strmatch.in");
ofstream out("strmatch.out");

int main() {
	in >> substr >> input;
	vector<int> result = KMP(input, substr);
	out << result.size() << '\n';
	for (unsigned int i = 0; i < result.size(); i++) out << result.at(i) << ' ';
}