Cod sursa(job #798585)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 16 octombrie 2012 19:42:10
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb

#include <cstdio>

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

char a [MAX_SIZE];
int a_length;
char b [MAX_SIZE];
int b_length;

int partial [MAX_SIZE];
int output [MAX_PRINT];
int *add_match(output);
int matches;

inline int length (char *string)
{
	int length, left(0), right(MAX_SIZE), middle((left + right) >> 1);
	while (true)
	{
		if (string[middle])
		{
			left = middle + 1;
			if (!string[left])
			{
				length = left + 1;
				break;
			}
		}
		else
		{
			right = middle;
			if (string[middle - 1])
			{
				length = middle;
				break;
			}
		}
		middle = (left + right) >> 1;
	}
}

inline void read (void)
{
	std::freopen("strmatch.in","r",stdin);
	std::scanf("%s%s",a,b);
	a_length = length(a);
	b_length = length(b);
	std::fclose(stdout);
}

inline void print (void)
{
	std::freopen("strmatch.out","w",stdout);
	std::printf("%d\n",matches);
	for (int *iterator(output) ; iterator < add_match ; ++iterator)
		std::printf("%d ",*iterator);
	std::putchar('\n');
	std::fclose(stdout);
}

inline void partial_match (void)
{
	*partial = -1;
	partial[1] = 0;
	int prefix(0), index(2);
	while (index < a_length)
	{
		if (a[index - 1] == a[prefix])
		{
			++prefix;
			partial[index] = prefix;
			++index;
		}
		else if (prefix > 0)
			prefix = partial[prefix];
		else
			++index;
	}
}

inline void  KnuthMorrisPratt (void)
{
	int a_index(0), b_index(0);
	while (b_index + a_index < b_length)
	{
		if (a[a_index] == b[b_index + a_index])
		{
			++a_index;
			if (a_index == a_length)
			{
				++matches;
				if (matches <= MAX_PRINT)
				{
					*add_match = b_index;
					++add_match;
				}
				a_index = 0;
				++b_index;
			}
		}
		else
		{
			b_index = b_index + a_index - partial[a_index];
			if (partial[a_index] > 0)
				a_index = partial[a_index];
			else
				a_index = 0;
		}
	}
}

int main (void)
{
	read();
	partial_match();
	KnuthMorrisPratt();
	print();
	return 0;
}