Cod sursa(job #153208)

Utilizator rethosPaicu Alexandru rethos Data 10 martie 2008 11:43:23
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <stdio.h>
#include <string.h>
#define NMAX 2000001
#define p 97
#define mod1 100007
#define mod2 100027
int match[NMAX];
int main()
{ freopen("strmatch.in","rt",stdin);
  freopen("strmatch.out","wt",stdout);
  char a[NMAX],b[NMAX];
  long na,nb,hash1,hash2,cod1,cod2,p1,p2;
  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))*p+b[i])%mod1;
	  hash2=((hash2-(b[i-na]*p2))*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;
}