Cod sursa(job #153237)

Utilizator rethosPaicu Alexandru rethos Data 10 martie 2008 12:19:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <string.h>
#define NMAX 2000001
#define p 97
#define mod1 100007
#define mod2 100021
char match[NMAX];
char a[NMAX],b[NMAX];
long na,nb,hash1,hash2,cod1,cod2,p1,p2;
int main()
{ freopen("strmatch.in","rt",stdin);
  freopen("strmatch.out","wt",stdout);
  scanf("%s %s",a,b);
  long i;
  p1=1,p2=1;
  cod1=0,cod2=0;
  na=strlen(a),nb=strlen(b);
  if (na>nb)
	{ printf("0");
	  return 0;
	}
  for (i=0;i<na;i++)
	{ cod1=(cod1*p+a[i])%mod1;
	  cod2=(cod2*p+a[i])%mod2;
	  if (i)
		 p1=(p1*p)%mod1,
		 p2=(p2*p)%mod2;

	}
  hash1=hash2=0;
  for (i=0;i<na;i++)
	 hash1=(hash1*p+b[i])%mod1,
	 hash2=(hash2*p+b[i])%mod2;
  long nr=0;
  if (cod1==hash1&&cod2==hash2)  match[0]=1,nr++;
  for (i=na;i<nb;i++)
	{ hash1=((hash1-(b[i-na]*p1)%mod1+mod1)*p+b[i])%mod1;
	  hash2=((hash2-(b[i-na]*p2)%mod2+mod2)*p+b[i])%mod2;
	  if (hash1==cod1&&hash2==cod2)
		 nr++,match[i-na+1]=1;
	}
  printf("%ld\n",nr);
  nr=0,i=0;
  while (i<nb&&nr<1000)
	{ if (match[i]==1)
		  printf("%ld ",i),nr++;
	  i++;
	}
  fclose(stdin);
  fclose(stdout);
  return 0;
}