Cod sursa(job #896519)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 27 februarie 2013 15:59:41
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<cstring>
#include<cstdio>
char a[2000013],b[2000013];
int na,nb,i,j,ca,cb,da,db,sol[1001],nsol,p,q;
inline int cod(char c)
{
	int x;
	if('a'<=c && c<='z')x=10+(int)c-(int)'a';
	else if('A'<=x && x<='Z')x=10+(int)c-(int)'A'+26;
	else x=c-(int)'0';
	return x;
}
/*inline bool check(int k)
{
	int i;
	for(i=0;i<nb;++i)
		if(a[i+k]!=b[i])return 0;
	return 1;
}*/
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(b);nb=strlen(b);
	gets(a);na=strlen(a);
	if(na<nb){printf("0");return 0;}
	ca=cb=da=db=0;
	p=q=1;
	for(i=1;i<nb;++i){p=(p*23)%666013;q=(q*19)%666011;}
	for(i=0;i<nb;++i)
	{
		ca=(ca*23+cod(a[i]))%666013;
		cb=(cb*23+cod(b[i]))%666013;
		da=(da*19+cod(a[i]))%666011;
		db=(db*19+cod(b[i]))%666011;
	}
	i=0;
	do
	{
		if(ca==cb && da==db)
			/*if(check(i))*/
			{
				++nsol;
				if(nsol<1001)sol[nsol-1]=i;
			}
		ca=(ca-(p*cod(a[i]))%666013+666013)%666013;
		ca=(ca*23+cod(a[i+nb]))%666013;
		da=(da-(q*cod(a[i]))%666011+666011)%666011;
		da=(da*19+cod(a[i+nb]))%666011;
		++i;
	}while(i+nb<=na);
	printf("%d\n",nsol);
	if(nsol>1000)nsol=1000;
	for(i=0;i<nsol;++i)printf("%d ",sol[i]);
	return 0;
}