Cod sursa(job #2958821)

Utilizator StasBrega Stanislav Stas Data 28 decembrie 2022 15:05:01
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

vector<int> pref(string &p)
{
	int m = p.size(), k = -1;

	vector<int> pref(m);
	pref[0] = 0;

	for (int i = 1; i < m; ++i)
	{
		while (k != -1 && p[k + 1] != p[i])
			k = pref[k];
		if (p[k + 1] == p[i])
			k++;
		pref[i] = k;
	}

	return pref;
}

void kmp(string &t, string &p)
{
	vector<int> prefix = pref(p);
	vector<int> potriviri;

	int k = -1, n = t.size(), m = p.size();
	for (int i = 0; i < n; ++i)
	{
		while (k != -1 && p[k + 1] != t[i])
			k = prefix[k];
		if (p[k + 1] == t[i])
			k++;
		if (k == m - 1)
		{
			k = prefix[k];
			potriviri.push_back(i - m + 1);
		}
	}

	cout << potriviri.size() << '\n';
	for(int i = 0; i < potriviri.size() && i < 1000; ++i)
		cout << potriviri[i] << ' ';
}

int main()
{
	string a, b; cin >> a >> b;
	kmp(b, a);

	return 0;
}