Cod sursa(job #935414)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 3 aprilie 2013 13:52:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb

#include <cstdio>

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

char a [MAX_SIZE];
char b [MAX_SIZE];
int dp [MAX_SIZE];
int match [MAX_M];
int matches, lena, lenb;

inline int len (const char s [ ])
{
	int left(0), right(MAX_SIZE - 1), middle((left + right) >> 1);
	while (left < right)
	{
		if (s[middle])
			left = middle + 1;
		else
			right = middle;
		middle = (left + right) >> 1;
	}
	return middle;
}

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

inline void print (void)
{
	std::freopen("strmatch.out","w",stdout);
	std::printf("%d\n",matches);
	if (matches > 1000)
		matches = 1000;
	for (int i(0) ; i < matches ; ++i)
		std::printf("%d ",match[i]);
	std::putchar('\n');
	std::fclose(stdout);
}

inline void compute_border (void)
{
	int i(0), j(-1);
	dp[0] = -1;
	while (i < lena)
	{
		while (j >= 0 && a[i] != a[j])
			j = dp[j];
		++j;
		++i;
		dp[i] = j;
	}
}

inline void KnuthMorrisPratt (void)
{
	int i(0), j(0);
	while (i < lenb)
	{
		while (j >= 0 && a[j] != b[i])
			j = dp[j];
		++j;
		++i;
		if (j == lena)
		{
			if (matches < 1000)
				match[matches] = i - j;
			j = dp[j];
			++matches;
		}
	}
}

int main (void)
{
	read();
	lena = len(a);
	lenb = len(b);
	compute_border();
	KnuthMorrisPratt();
	print();
	return 0;
}