Cod sursa(job #795021)

Utilizator radustn92Radu Stancu radustn92 Data 7 octombrie 2012 15:03:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
#define LMAX 1005
char A[NMAX],B[NMAX];
int sol[LMAX],r;
int n,m,pi[NMAX];
inline int check(char x)
{
	return (x>='0' && x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z') ;
}
void read()
{
	fgets(A+1,NMAX,stdin);
	fgets(B+1,NMAX,stdin);
	while (check(A[n+1])) n++;
	while (check(B[m+1])) m++;
}
void precompute()
{
	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 solve()
{
	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)
		{
			if (r<1000)
				sol[++r]=i-n+1;
			q=pi[q];
		}
	}
	printf("%d\n",r);
	for (i=1; i<=r; i++)
		printf("%d ",sol[i]-1);
	printf("\n");
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	read();
	precompute();
	solve();
	return 0;
}