Cod sursa(job #434197)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 5 aprilie 2010 12:24:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#define LMAX 2000005
#define KMAX 1005
char A[LMAX],B[LMAX];
int n,m,pi[LMAX],r,sol[KMAX];
inline int ok(char x)
{
	return (x>='A' && x<='Z') || (x>='a' && x<='z') || (x>='0' && x<='9');
}
void prefix()
{
	int i,q=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 match()
{
	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)
		{
			r++;
			if (r<=1000)
				sol[r]=i-n;
		}
	}
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void show()
{
	printf("%d\n",r);
	int i,t=min(r,1000);
	for (i=1; i<=t; i++)
		printf("%d ",sol[i]);
	printf("\n");
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(A+1,LMAX,stdin);
	fgets(B+1,LMAX,stdin);
	while (ok(A[n+1])) n++;
	while (ok(B[m+1])) m++;
	prefix();
	match();
	show();
	return 0;
}