Cod sursa(job #683403)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 20 februarie 2012 16:32:31
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
using namespace std;

ifstream fi ("kmp.in");
ofstream fo ("kmp.out");

const int dim = 2000005; 
char A[dim], B[dim];
int P[dim], R[1005], N;

void cit ()
{
	fi >> A+1 >> B+1;
}

void prf ()
{
	int k = 0;
	for (int i = 2; A[i] != 0; i++)
	{
		while (k > 0 && A[k + 1] != A[i])
			k = P[k];
		if (A[k + 1] == A[i])
			k++;
		P[i] = k;
	}
}

void kmp ()
{
	int k = 0;
	for (int i = 1; B[i] != 0; i++)
	{
		while (k > 0 && A[k + 1] != B[i])
			k = P[k];
		if (A[k + 1] == B[i])
			k++;
		if (A[k + 1] == 0)
		{
			N++;
			if (N <= 1000)
				R[N] = i - k;
		}
	}
}

void afi ()
{
	fo << N << '\n';
	if (N > 1000) N = 1000;
	for (int i = 1; i <= N; i++)
		fo << R[i] << ' '; 
}

int main ()
{
	cit ();
	prf ();
	kmp ();	
	afi ();
	return 0;
}