Cod sursa(job #348317)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 15 septembrie 2009 11:29:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>
#define P 1<<21
#define Q 1<<10
char M[P],N[P];
int m,n,pi[P],nr,sol[P];
inline int lit(char x)
{
	return (x>='A' && x<='Z') || (x>='a' && x<='z') ||
		   (x>='0' && x<='9');
}
void calc_prefix()//cel mai lung prefix care e si sufix pt sirul N
{
	int k=0,i;
	for (i=2; i<=n; i++)
	{
		while (k>0 && N[k+1]!=N[i])k=pi[k];
	/*"trec la configuratiile anterioare de prefixe 
	care sunt si sufixe" si gasesc o potrivire*/
		if (N[k+1]==N[i])k++;//"potrivire cu configuratia anterioara"
		pi[i]=k;
	}
}
void kmp()
{
	int i,q=0;
	for (i=1; i<=m; i++)
	{
		while  (q>0 && N[q+1] != M[i]) q=pi[q];//se incearca potriviri
		if ( N[q+1] == M[i]) q++;//potrivire pt primele q pozitii
		if ( q == n)//potrivire perfecta
		{
			nr++;
			if (nr<=1000)sol[nr]=i-n;
		}
	}
}
inline int min(int a,int b)
{
	if (a<b)
		return a;
	return b;
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(N+1,P,stdin);
	while (lit(N[n+1])) n++;
	fgets(M+1,P,stdin);
	while (lit(M[m+1])) m++;
	calc_prefix();
	kmp();
	printf("%d\n",nr);
	int i,t=min(nr,1000);
	for (int i=1; i<=t; i++)
		printf("%d ",sol[i]);
	return 0;
}