Cod sursa(job #2852880)

Utilizator Radu_marioRadu Mario Radu_mario Data 19 februarie 2022 17:37:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream file_in("strmatch.in");
ofstream file_out("strmatch.out");

size_t i, j, CNT;
vector<size_t> AP;

void Init_LPS(string PAT, size_t M, size_t* LPS)
{
	size_t LEN = 0;
	LPS[LEN] = 0;
	i = 1;

	while (i < M)
	{
		if (PAT[LEN] == PAT[i]) ++LEN, LPS[i++] = LEN;
		else if (LEN) LEN = LPS[LEN - 1];
		else LPS[i++] = 0;
	}
}

void KMP(string PAT, string TXT)
{
	size_t M = PAT.length();
	size_t N = TXT.length();

	size_t* LPS = new size_t[M];
	Init_LPS(PAT, M, LPS);

	i = 0, j = 0;
	while (i < N)
	{
		if (TXT[i] == PAT[j]) ++i, ++j;
		if (j == M)
		{
			++CNT;
			AP.push_back(i - j);
			j = LPS[j - 1];
		}
		else if (i < N && TXT[i] != PAT[j])
		{
			if (j) j = LPS[j - 1];
			else ++i;
		}
	}
}

int main()
{
	string A, B;
	file_in >> A >> B;
	KMP(A, B);

	file_out << CNT << '\n';
	for (auto it : AP) file_out << it << ' ';
	return 0;
}