Cod sursa(job #800876)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 22 octombrie 2012 20:37:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 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 border [MAX_SIZE];

int match [MAX_PRINT];
int *add_match(match);
int matches;

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

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

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

inline void preprocess (void)
{
	*border = -1;
	int i(0), j(-1);
	while (i < a_length)
	{
		while (j >= 0 && a[i] != a[j])
			j = border[j];
		++i;
		++j;
		border[i] = j;
	}
	
}

inline void KnuthMorrisPratt (void)
{
	preprocess();
	int i(0), j(0);
	while (i < b_length)
	{
		while (j >= 0 && a[j] != b[i])
			j = border[j];
		++i;
		++j;
		if (j == a_length)
		{
			++matches;
			if (matches <= MAX_PRINT)
			{
				*add_match = i - j;
				++add_match;
			}
			j = border[j];
		}
	}
}

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