Cod sursa(job #2717343)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 7 martie 2021 10:53:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 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=0;i < 1000 && i < sol.size();i++)
		cout << sol[i] << ' ';
    return 0;
}