Cod sursa(job #193625)

Utilizator raduzerRadu Zernoveanu raduzer Data 5 iunie 2008 15:58:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <stdio.h>
#include <string.h>

int n,m,i,j,c[2000010];
unsigned int v,v2,k;
char a[2000020],b[2000020];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(a,2000010,stdin);
	fgets(b,2000010,stdin);
	n=strlen(a)-1;
	m=strlen(b)-1;
	for (i=n-1, k=1; i>=0; --i, k*=65) v+=(a[i]-'0')*k;
	for (i=n-1, k=1; i>=0; --i, k*=65) v2+=(b[i]-'0')*k;
	if (v==v2) c[++c[0]]=0;
	for (i=n; i<m; ++i)
	{
		v2=v2*65+(b[i]-'0');
		v2-=(b[i-n]-'0')*k;
		if (v==v2) c[++c[0]]=i-n+1;
	}
	printf("%d\n",c[0]);
	for (i=1; i<=c[0] && i<=1000; ++i) printf("%d ",c[i]);
	return 0;
}