Cod sursa(job #337813)

Utilizator ilincaSorescu Ilinca ilinca Data 5 august 2009 00:48:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <stdio.h> 

#define pmax 2000000


char A [pmax+5], B [pmax+5];
int n, m, nrs, pos [1005], pi [pmax+5];


void scan ()
{
	gets (A+1);
	gets (B+1);
	for (n=1; A [n]; ++n);
	for (m=1; B [m]; ++m); //fprintf(stderr, "n=%d m=%d\n", n, m);  
}

void form_pi ()
{
	int i, q=0;
	pi [1]=0;
	for (i=2; i <= n; ++i) 
	{
		while (q && (A [q+1] != A [i])) 
			q=pi [q];
		if (A [q+1] == A [i]) 
			++q;
		pi [i]=q;
	}
}

void kmp ()
{
	int i, q=0;
	for (i=1; i <= m; ++i)
	{
		while (q && (A [q+1] != B [i])) 
			q=pi [q];
		if (A [q+1] == B [i]) 
			++q;
		if (q == n-1)
		{
			//q=pi [n-1];
			++nrs;
			if (nrs <= 1000) 
				pos [nrs]=i-n+1;
		}	
	}	
}

void print ()
{
	int i, k=(nrs < 1000)? nrs:1000;
	printf ("%d\n", nrs);
	for (i=1; i <= k; ++i)
	       printf ("%d ", pos [i]);	
	printf ("\n");
}

int main ()
{
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	scan ();
	form_pi ();
	kmp ();
	print ();
	return 0;
}