Cod sursa(job #1379238)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 6 martie 2015 17:07:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb

#include <fstream>

const int MAX_SIZE(2000001);
const int MAX_M(1000);

char a [MAX_SIZE], b [MAX_SIZE];
int Border [MAX_SIZE];
int Total_matches, Matches [MAX_M];

inline void Read (void)
{
	std::ifstream input("strmatch.in");
	input >> a >> b;
	input.close();
}

inline void Print (void)
{
	std::ofstream output("strmatch.out");
	output << Total_matches << '\n';
	for (int i(0) ; i < Total_matches && i < MAX_M ; ++i)
		output << Matches[i] << ' ';
	output.put('\n');
	output.close();
}

inline void KnuthMorrisPratt (void)
{
	Border[0] = -1;
	int i(0), j(-1);
	while (a[i])
	{
		while (j >= 0 && a[i] != a[j])
			j = Border[j];
		++i;
		++j;
		Border[i] = j;
	}
	i = j = 0;
	while (b[i])
	{
		while (j >= 0 && a[j] != b[i])
			j = Border[j];
		++i;
		++j;
		if (!a[j])
		{
			if (Total_matches < MAX_M)
				Matches[Total_matches] = i - j;
			++Total_matches;
			j = Border[j];
		}
	}
}

int main (void)
{
	Read();
	KnuthMorrisPratt();
	Print();
	return 0;
}