Cod sursa(job #2374710)

Utilizator tangerine515Alex Anton tangerine515 Data 7 martie 2019 20:05:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cassert>
#include <fstream>
#include <string>
#include <vector>

std::fstream fi("strmatch.in", std::ios::in);
std::fstream fo("strmatch.out", std::ios::out);

using result = struct { unsigned cnt = 0; std::vector<unsigned> patfind; };

void patpcomp(std::string const& s, unsigned* pf) {
    pf[0] = 0;
    for (size_t i = 1, l = 0; i < s.length();)
        if (s.at(i) == s.at(l))
			pf[i++] = ++l;
		else
			if (l != 0) l = pf[l - 1];
			else pf[i++] = 0;
}

static result kmpratt(std::string const& sa, std::string const& sb, unsigned* pat) {
	result res = { 0 };
	unsigned m = sa.length(), n = sb.length();
	for (size_t i = 0, j = 0; i < n;) {
        if (sa.at(j) == sb.at(i)) { i++; j++; }
        if (j == m) {
			res.patfind.push_back(i - j);
			res.cnt++;
			j = pat[j - 1];
        } else if (i < n && sa.at(j) != sb.at(i)) {
			if (j != 0) j = pat[j - 1];
			else i++;
        }
	}
	return res;
}

int main (void) {
	std::string str1, str2;
	assert(std::getline(fi, str1));
	assert(std::getline(fi, str2));
	unsigned* pattern = new unsigned[str1.length()]; patpcomp(str1, pattern);
	result val = kmpratt(str1, str2, pattern);
	assert(fo << val.cnt << "\n");
	for (const auto& i : val.patfind)
		assert(fo << i << " ");
	return 0;
}