Cod sursa(job #629519)

Utilizator SmarandaMaria Pandele Smaranda Data 3 noiembrie 2011 14:20:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<cstring>
#define B 67
#define P 666013
using namespace std;
char a[2000002];
char b[2000002];
long pow_b[2000002];
long af[1001];
long comparare(long st  , long dr)
{
	long i,j;
	for (i=st,j=0;i<dr;i++,j++)
		if (a[i]!=b[j])
			return 0;
	return 1;
}

int main()
{
	long l,nr=0,w,hashb=0,hasha=0,la,num=0,i;
	
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	gets(b);
	gets(a);
	l=strlen(b);
	la=strlen(a);
	for (i=0;i<l;i++)
	{
		hashb=(hashb*B+b[i])%P;
		hasha=(hasha*B+a[i])%P;
	}
	pow_b[0]=1;
	for (i=1;i<=la;i++)
		pow_b[i]=(pow_b[i-1]*B)%P;
	if (hashb==hasha)
		//if (comparare(0,l)==1)
		{
			num++;
			af[num]=0;
		}
	for (i=1;i<la;i++)
	{
		//printf("%ld %ld\n",hasha,hashb);
		hasha=((hasha-(a[i-1]*pow_b[l-1])%P+P)%P)%P;
		hasha=hasha*B%P;
		hasha=(hasha+a[i+l-1])%P;
		if (hashb==hasha)
			//if (comparare(i,i+l)==1)
			{
				num++;
				if (num<=1000)
				af[num]=i;
			}
	}
	printf("%ld\n",num);
	if (num>1000)
		num=1000;
	for (i=1;i<=num;i++)
		printf("%ld ",af[i]);
	if (num)
	printf("\n");
	return 0;
}