Cod sursa(job #2436177)

Utilizator RaulG99Gioanca Raul RaulG99 Data 4 iulie 2019 20:15:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int a, b, d, x, y, n, m, nr;
int pi[1000];
int pos[1000];
string N, M;

void Prefix()
{
	int k = 0;
	pi[1] = 0;

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

		if (N[k] == N[i-1])
		{
			k = k + 1;
		}
		
		pi[i] = k;
	}
}

void Kmp()
{
	int q = 0;
	
	for (int i = 1; i <= m; i++)
	{
		if (q > 0 && (N[q] != M[i-1]) )
		{
			q = pi[q];
		}

		if (N[q] == M[i-1])
		{
			q = q + 1;
		}
		if (q == n)
		{
			q = pi[n];
			nr++;
			if (nr <= 1000)
			{
				pos[nr] = i - n;
			}
		}

	}
}


int main()
{
	f >> N >> M;
	n = N.size();
	m = M.size();

	Prefix();
	Kmp();

	g << nr<<"\n";

	if (nr > 1000)
		nr = 1000;

	for (int i = 1; i <= nr; i++)
		g << pos[i] << " ";

}