Cod sursa(job #169900)

Utilizator znakeuJurba Andrei znakeu Data 2 aprilie 2008 10:47:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>
#include <string.h>
#define MAXL 2000100
char A[MAXL],B[MAXL];
int pi[MAXL];
int R[1005],r;
int nA,nB;

void calcpi()
{
	int k=0,i;
	pi[1]=0;
	for (i=2; i<=nA; ++i)
	{
		while (k>0 && A[k+1]!=A[i])
			k=pi[k];
		if (A[k+1]==A[i])
			++k;
		pi[i]=k;
	}
}

void rezolv()
{
	int k=0,i;
	for (i=1; i<=nB; ++i)
	{
		while (k>0 && A[k+1]!=B[i])
			k=pi[k];
		if (A[k+1]==B[i])
			++k;
		if (k==nA)
		{
			if (r<1000)
				R[r++]=i-nA;
			else
				r++;
		}
	}
}

void afisare()
{
	printf("%d\n",r);
	if (r)
	{
		printf("%d",R[0]);
		for (int i=1; i<r && i<1000; i++)
			printf(" %d",R[i]);
		printf("\n");	
	}
}
void citire()
{
	fgets(A+1,MAXL,stdin);
	fgets(B+1,MAXL,stdin);

	nA=strlen(A+1); nA++;
	while ( !( (A[nA]>='A' && A[nA]<='Z') || (A[nA]>='a' && A[nA]<='z') || (A[nA]>='0' && A[nA]<='9')) )
		nA--;

	nB=strlen(B+1); nB++;
	while ( !( (B[nB]>='A' && B[nB]<='Z') || (B[nB]>='a' && B[nB]<='z') || (B[nB]>='0' && B[nB]<='9')) )
		nB--;
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	citire();
	calcpi();
	rezolv();
	afisare();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}