Cod sursa(job #2717340)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 7 martie 2021 10:49:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

string N, M;
int n, m;
int pi[2000005];
vector<int> sol;

void precalc()
{
	int k = -1;

	pi[0] = -1;
	for (int i=1;i<n;i++)
	{
		while (k != -1 && N[k+1] != N[i])
			k = pi[k];
		if (N[k+1] == N[i])
			k++;
		pi[i] = k;
	}
}

void kmp()
{
	int q = -1;

	for (int i=0;i<m;i++)
	{
		while (q != -1 && N[q + 1] != M[i])
			q = pi[q];
		if (N[q + 1] == M[i])
			q = q + 1;
		if (q == n - 1)
			sol.push_back(i - n + 1);
	}
}

int main()
{
	cin >> N >> M;

	n = N.length();
	m = M.length();

	precalc();
	kmp();
	cout << sol.size() << '\n';
	for (int i : sol)
		cout << i << ' ';
    return 0;
}