Cod sursa(job #2718660)

Utilizator zerolightningIon Bobescu zerolightning Data 8 martie 2021 22:58:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

int N, M;

void calculatePrefixVector(string& pattern, vector<int>& prefixVector)
{
	prefixVector[0] = 0;

	int len = 0;
	for (int i = 1; i < N;)
	{
		if (pattern[i] == pattern[len])
		{
			len++;
			prefixVector[i] = len;
			i++;
		}
		else
		{
			if (len != 0)
			{
				len = prefixVector[len - 1];
			}
			else
			{
				prefixVector[i] = 0;
				i++;
			}
		}
	}
}

void solve(string& pattern, string& space, int& K, vector<int>& solutions)
{
	vector<int> prefixVector(N);
	calculatePrefixVector(pattern, prefixVector);

	int j = 0;
	for (int i = 0; i < M;)
	{
		if (pattern[j] == space[i])
		{
			i++;
			j++;
		}
		else
		{
			if (j > 0)
			{
				j = prefixVector[j - 1];
			}
			else
			{
				i++;
			}
		}

		if (j == N)
		{
			j = prefixVector[j - 1];
			K++;
			solutions.push_back(i - N);
		}
	}
}

int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	// Program
	string pattern, space;
	f >> pattern >> space;
	N = pattern.size();
	M = space.size();

	int K = 0;
	vector<int> solutions;
	solve(pattern, space, K, solutions);
	g << K << endl;
	int toShow = min(K, 1000);
	for (int i = 0; i < toShow; i++)
	{
		g << solutions[i] << " ";
	}
	// Exit
	f.close();
	g.close();
	return 0;
}