Cod sursa(job #2761192)

Utilizator raikadoCri Lu raikado Data 1 iulie 2021 01:33:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;


vector<int> kmp_table(const string &W)
{
	size_t N = W.size();
	vector<int> T(N + 1);
	int pos = 1, cnd = 0;

	T[0] = -1;
	while (pos < N) {
		if (W[pos] == W[cnd]) {
			T[pos] = T[cnd];
		} else {
			T[pos] = cnd;
			while (cnd >= 0 && W[pos] != W[cnd]) {
				cnd = T[cnd];
			}
		}
		pos++; cnd++;
	}
	T[pos] = cnd;

	return T;
}

vector<int> kmp_search(const string &S, const string &W, const size_t MAXN=1000) {
	int j = 0, k = 0;
	const vector<int> T = kmp_table(W);

	vector<int> P;

	while (j < S.size()) {
		if (W[k] == S[j]) {
			j++; k++;
			if (k == W.size()) {
				P.push_back(j - k);
				// if (P.size() == MAXN)
				// 	return P;
				k = T[k];
			}
		} else {
			k = T[k];
			if (k < 0) {
				j++; k++;
			}
		}
	}

	return P;
}

int main(int argc, char const *argv[])
{
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");

	string A, B;
	fin >> A >> B;

	cout << A << '\n' << B << endl;

	vector<int> P = kmp_search(B, A, 1000);
	fout << P.size() << '\n';
	for (int p : P) {
		fout << p << ' ';
	}

	return 0;
}