Cod sursa(job #2958834)

Utilizator StasBrega Stanislav Stas Data 28 decembrie 2022 15:52:17
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <unordered_set>
#include <algorithm>

using namespace std;

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

void automata(string& t, string& p)
{
	int n = t.size(), m = p.size();

	unordered_set<char> dict(t.begin(), t.end());
	vector<map<char, int>> states(m + 1);

	for(int q = 0; q <= m; ++q)
		for (char ch : dict)
		{
			string pref = p.substr(0, q) + ch;
			int k = min(m, q + 1);
			while (p.substr(0, k) != pref.substr(q + 1 - k, k))
				k--;
			states[q][ch] = k;
		}

	vector<int> potriviri;

	for (int i = 0, q = 0; i < n; ++i)
	{
		q = states[q][t[i]];
		if (q == m)
			potriviri.push_back(i - m + 1);
	}

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

void kmp(string &t, string &p)
{
	int n = t.size(), m = p.size();

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

	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] << ' ';
}

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

	return 0;
}