Cod sursa(job #2958824)

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

using namespace std;

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

void kmp(string &t, string &p)
{

}

int main()
{
	string t, p; cin >> p >> t;

	int n = t.size(), m = p.size();

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

	for (int i = 1, k = -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;
	}

	vector<int> potriviri;

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

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

	return 0;
}