Cod sursa(job #2470563)

Utilizator ShayTeodor Matei Shay Data 9 octombrie 2019 14:56:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>
#include <string>

void make_prefix(std::vector<int> &pi, std::string &A) {
	int k = 0, i, n = A.size();
	pi.resize(n);

	for (i = 1, pi[0] = 0; i < n ; ++i) {
		while ( k && A[k] != A[i]) {
			k = pi[k - 1];
		}

		if (A[k] == A[i]) {
			++k;
		}

		pi[i] = k;
	}
}

std::vector<int> match(std::vector<int> &pi, std::string &A, std::string &B, int &N) {
	int k = 0;
	int n = A.size();
	int m = B.size();
	std::vector<int> position;

	for (int i = 0 ; i < m ; ++i) {
		while (k && A[k] != B[i]) {
			k = pi[k - 1];
		}

		if (A[k] == B[i]) {
			++k;
		}

		if (k == n && ++N <= 1000) {
			position.push_back(i - n + 1);
		}
	}

	return position;
}

int main() {
	std::string A, B;
	std::ifstream in("strmatch.in");
	std::ofstream out("strmatch.out");
	std::ios::sync_with_stdio(false);
	int N = 0;

	in >> A >> B;
	std::vector<int> pi;
	make_prefix(pi, A);
	std::vector<int> position = match(pi, A, B, N);

	out << N << '\n';

	for (unsigned int i = 0 ; i < position.size() ; ++i) {
		out << position[i] << " ";
	}

	in.close();
	out.close();
	return 0;
}