Cod sursa(job #2702597)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 4 februarie 2021 21:34:08
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <string>
#include <fstream>
#include <vector>
using namespace std;

vector<int> build_kmp_table(string w);

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

	string a, b;
	fin >> a >> b;

	int na = a.length();
	int nb = b.length();

	vector<int> t = build_kmp_table(a);

	vector<int> results;
	results.reserve(nb-na+1);

	int s = 0;
	int i = 0;

	while (s < nb) {
		if (i == na) {
			results.push_back(s);
			s = s + i - t[i-1]; 
			i = t[i-1];
		}
		else if (b[s+i] == a[i]) {
			++i;
		}
		else if (i == 0) {
			s++;
		}
		else {
			s = s + i - t[i-1];
			i = t[i-1];
		}
	}

	fout << results.size() << endl;
	for (int pos : results)
		fout << pos << ' ';
	fout << endl;

	return 0;
}

vector<int> build_kmp_table(string w)
{
	int n = w.length();
	vector<int> t(n,-1);

	t[0] = 0;

	for (int i = 1; i < n; ++i) {
		int k = t[i-1];
		while (t[i] == -1) {
			if (k == 0)
				t[i] = w[i] == w[0] ? 1 : 0;
			else if (w[i] == w[k])
				t[i] = k+1;
			else
				k = t[k-1];
		}
	}

	return t;
}