Cod sursa(job #2596062)

Utilizator warriorscatsfirestarBarbut-Dica Sami warriorscatsfirestar Data 9 aprilie 2020 10:44:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
// KMP2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <fstream>
#include <vector>
#include <string>
#include <set>
#include <iterator>
#include <algorithm>

constexpr auto NMAX = 1000;


std::ifstream fin ("strmatch.in");
std::ofstream fout ("strmatch.out");

int n, m;
std::string text, pattern;
std::vector <int> lps;
std::set <int> Store;


inline void Compute_LPS () {
	int len = 0, i = 1;

	while (i < m) {
		if (pattern[i] == pattern[len])
			++ len, lps[i] = len, ++ i;
		else {
			if (len) len = lps[len - 1];
			else lps[i] = 0, ++ i;
		}
	}
}

inline void KMP_Search () {
	int i = 0, j = 0;
	n = (int)text.size (), m = (int)pattern.size ();
	lps.assign (m, 0);
	if (n < m) goto end;

	Compute_LPS ();
	while (i < n) {
		if (text[i] == pattern[j])
			++ i, ++ j;
		if (j == m) {
			if ((int)Store.size () < NMAX)
				Store.insert (i - j), j = lps[j - 1];
			else goto end;
		}
		else if (i < n && text[i] != pattern[j]) {
			if (j) j = lps[j - 1];
			else ++ i;
		}
	}
	end : ;
}


int main () {
	fin >> pattern >> text;
	KMP_Search ();
	fout << Store.size () << "\n";
	std::copy (Store.begin (), Store.end (), std::ostream_iterator <int> (fout, " "));

	fin.close (), fout.close ();
	return 0;
}


// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file