Cod sursa(job #2783532)

Utilizator sebimihMihalache Sebastian sebimih Data 14 octombrie 2021 17:40:09
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int MAXN = (int)2e6 + 5;

int LPS[MAXN];

void calculateLPS(string& p)
{
	LPS[0] = -1;
	int indexPrefix = -1;

	for (int indexSufix = 1; indexSufix < p.size(); indexSufix++)
	{
		while (indexPrefix > -1 && p[indexPrefix + 1] != p[indexSufix])
		{
			indexPrefix = LPS[indexPrefix];
		}

		if (p[indexPrefix + 1] == p[indexSufix])
		{
			indexPrefix++;
		}

		LPS[indexSufix] = indexPrefix;
	}
}

int main()
{
	string model, text;
	fin >> model >> text;

	calculateLPS(model);

	int cnt = 0;
	vector<int> pozitii;
	pozitii.reserve(1005);

	int indexModel = -1;
	for (int indexText = 0; indexText < text.size(); indexText++)
	{
		while (indexModel > -1 && model[indexModel + 1] != text[indexText])
		{
			indexModel = LPS[indexModel];
		}

		if (model[indexModel + 1] == text[indexText])
		{
			indexModel++;
		}

		if (indexModel == model.size() - 1)
		{
			cnt++;
			indexModel = LPS[indexModel];

			if (cnt <= 1000)
				pozitii.push_back(indexText - model.size() + 1);
		}
	}

	cout << cnt << '\n';
	for (int poz : pozitii)
	{
		cout << poz << ' ';
	}
}

/*

	ABA

	0 1 2 3 4 5 6 7 8 9 10
	C A B B C A B A B A  B

*/