Cod sursa(job #1759924)

Utilizator andreioneaAndrei Onea andreionea Data 19 septembrie 2016 23:49:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>

#include <iostream>

struct file_manip {

	std::ifstream fin;
	std::ofstream fout;

	file_manip(const char* filename) {
		std::string infilename  = std::string(filename) + ".in";
		std::string outfilename = std::string(filename) + ".out";
		fin.open(infilename.c_str());
		fout.open(outfilename.c_str());
	}

	template <class T>
	file_manip& operator << (const T& rhs) {
		fout << rhs;
		return *this;
	}
	template <class T>
	file_manip& operator >> (T& rhs) {
		fin >> rhs;
		return *this;
	}
};

class MatchComputer
{
	const std::string& str;	
	std::vector<int> prefix;

	void PrecomputePrefixes();
public:
	MatchComputer(const std::string& str) : str(str) {PrecomputePrefixes();}
	std::vector<int> FindMatches(const std::string& other) const;
};

void MatchComputer::PrecomputePrefixes()
{
	int curr_match = 0;
	prefix.reserve(str.size() + 1);
	prefix.push_back(-1);
	for (const char c : str) 
	{
		if (prefix.size() == 1) {
			prefix.push_back(0);
			continue;
		}
		while (str[curr_match] != c && curr_match > 0)
			curr_match = prefix[curr_match];
		if (str[curr_match] == c)
			++curr_match;
		prefix.push_back(curr_match);
	}
}
std::vector<int> MatchComputer::FindMatches(const std::string& other) const
{
	std::vector<int> ret;
	int curr_match = 0;
	int idx = 0;
	for (const char c : other) {
		while (str[curr_match] != c && curr_match > 0)
			curr_match = prefix[curr_match];
		if (str[curr_match] == c)
			++curr_match;
		if (curr_match == str.size()){
			ret.push_back(idx - str.size() + 1);
			curr_match = prefix[curr_match];
		}
		++idx;
	}
	return ret;
}

int main()
{
	file_manip fm("strmatch");
	std::string s1, s2;
	fm >> s1 >> s2;

	MatchComputer mc(s1);
	const auto matches = mc.FindMatches(s2);
	fm << matches.size() << "\n";
	for (const auto i : matches) {
		fm << i << " ";
	}
	return 0;
}