Cod sursa(job #2511229)

Utilizator DawlauAndrei Blahovici Dawlau Data 18 decembrie 2019 16:27:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
//#include "pch.h"
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

void buildPi(vector <int> &pi, const string &pattern) {

	int jIdx = -1;
	pi[0] = -1;

	for (int idx = 1; idx < (int)pattern.size(); ++idx) {

		while (jIdx != -1 and pattern[jIdx + 1] != pattern[idx])
			jIdx = pi[jIdx];

		if (pattern[jIdx + 1] == pattern[idx])
			++jIdx;
		pi[idx] = jIdx;
	}
}

int main() {

	string pattern, String;
	fin >> pattern >> String;

	vector <int> pi(pattern.size());
	buildPi(pi, pattern);

	vector <int> index;
	index.reserve(1000);

	int jIdx = -1;
	for (int idx = 0; idx < (int)String.size(); ++idx) {

		while (jIdx != -1 and String[idx] != pattern[jIdx + 1])
			jIdx = pi[jIdx];

		if (String[idx] == pattern[jIdx + 1])
			++jIdx;

		if (jIdx + 1 == (int)pattern.size() and index.size() < 1000)
			index.push_back(idx - pattern.size() + 1), jIdx = pi[jIdx];
	}

	fout << index.size() << '\n';
	for (const int &itm : index)
		fout << itm << ' ';
}