Cod sursa(job #195330)

Utilizator cipPaduraru Ciprian - Ionut cip Data 17 iunie 2008 18:02:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <cstring>

#define MAX_LENGTH	2000001

char N[MAX_LENGTH], M[MAX_LENGTH];
int n,m;
int PI[MAX_LENGTH];


void functiePrefix()
{
	int k=-1;
	PI[0]=0;
	for (int i=1;i<n;i++)
	{
		while(k>0 && (N[k+1] != N[i]))
			k = PI[k];

		if (N[k+1] == N[i])
			k++;

		PI[i] = k;
	}
}

void calculeazaSiruri()
{
	int Occurences[MAX_LENGTH];
	int iNrOccurences=0;

	int q = -1;
	for (int i=0;i<m;i++)
	{
		while(q > 0 && (N[q+1] != M[i]))
			q = PI[q];

		if (N[q+1] == M[i])
			q++;

		if (q == n-1)
		{
			Occurences[iNrOccurences++]=i-n+1;
			q = PI[q];
		}
	}

	printf("%d\n",iNrOccurences);
	if (iNrOccurences > 1000)
		iNrOccurences = 1000;
	for (int i=0;i<iNrOccurences;i++)
		printf("%d ",Occurences[i]);
	printf("\n");
}

int main() 
{
	freopen( "strmatch.in", "r", stdin );
	freopen( "strmatch.out", "w", stdout );

	scanf("%s\n",&N);
	scanf("%s\n",&M);

	n=strlen(N);
	m=strlen(M);

	functiePrefix();
	calculeazaSiruri();
		
	return 0;
}