Cod sursa(job #2063152)

Utilizator k.bruenDan Cojocaru k.bruen Data 11 noiembrie 2017 09:53:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <vector>

using std::string;
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");

string toMatch, matchIn;
std::vector<int> locations;

void match(string matchIn, string pattern);

int main() {
	in >> toMatch >> matchIn;

	match(matchIn, toMatch);

	out << locations.size() << '\n';
	for (int i = 0; i < locations.size() && i < 1000; ++i) {
		out << locations[i] << ' ';
	}

	return 0;
}

void match(string matchIn, string pattern) {
	// Calculare pozitii

	std::vector<int> pozitiiRepetare;
	pozitiiRepetare.resize(pattern.size(), 0);
	int patternSize = 0;

	for (int i = 1; i < pattern.size(); ++i) {
		if (pattern[i] == pattern[patternSize]) {
			pozitiiRepetare[i] = ++patternSize;
		}
		else {
			patternSize = 0;
		}
	}

	// Gasire substr = somehow = maybe = I hate this shit = I want home
	// AAAAAAAAAaaaaaand here I'm stuck
	// Fuuuuuuuuuuuuuuuuuuuck
	// Seriously, how the fuck am I supposed to do this?

	// Cancer.

	int positionInPattern = 0;

	for (int i = 0; i < matchIn.size(); ++i) {
		if (positionInPattern == pozitiiRepetare.size()) {
			locations.push_back(i - positionInPattern);
			positionInPattern = pozitiiRepetare[positionInPattern - 1];
		}

		if (matchIn[i] == pattern[positionInPattern]) positionInPattern++;
		else {
			positionInPattern = pozitiiRepetare[positionInPattern];
		}
	}
}