Cod sursa(job #1091713)

Utilizator pulseOvidiu Giorgi pulse Data 25 ianuarie 2014 22:46:22
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define NMAX 2000003

int n, m, num;
int table[NMAX];
char w[NMAX], s[NMAX];
queue <int> sol;

void ReadData ()
{
	scanf ("%s \n %s", w, s);
	n = strlen (s);
	m = strlen (w);
	w[m] = '#';
}

int Testing ()
{
	if (m > n) return 0;
	else return 1;
}

void Init_Table ()
{
	table[0] = -1;
	int i = 2, k = 0;
	while (i <= m)
	{
		if (w[i - 1] == w[k])
		{
			++k;
			table[i] = k;
			++i;
		}
		else if (k)
			k = table[k];
		else
		{
			table[i] = 0;
			++i;
		}
	}
}

void KMP ()
{
	int k = 0;
	for (int i = 0; k + i < n; )
	{
		if (s[k + i] == w[i])
		{
			if (i == m - 1)
			{
				num += 1;
				if (num <= 1000)
					sol.push(k);
			}
			++i;
		}
		else
		{
			k += i - table[i];
			i = (table[i] > -1) ? table[i] : 0;
		}
	}
}

void WriteData ()
{
	printf ("%d \n", num);
	while (!sol.empty())
	{
		printf ("%d ", sol.front());
		sol.pop();
	}
}

int main ()
{
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	ReadData();
	if (!Testing()) return 0;
	Init_Table();
	KMP();
	WriteData ();
	return 0;
}