Cod sursa(job #2958837)

Utilizator StasBrega Stanislav Stas Data 28 decembrie 2022 16:09:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 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 automataOptimized(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;
	}

	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)
		{
			int k = q - 1;
			while (k != -1 && p[k + 1] != ch)
				k = pref[k];
			if (p[k + 1] == ch)
				k++;
			states[q][ch] = k + 1;
		}

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

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

	automataOptimized(t, p);

	return 0;
}