Cod sursa(job #152472)

Utilizator AlxCojocaru Alexandru Alx Data 9 martie 2008 14:55:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <string.h>
using namespace std;
char a[2000005],b[2000005],mt[2000005];
long p=73,mod1=100007,mod2=100021,p1=1,p2=1,hashA1,hashA2,hash1,hash2;
int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 scanf("%s %s",&a,&b);
 long m=strlen(a),n=strlen(b),i,nr=0;
 if (m>n)
 {
  printf("0\n");
  return 0;
 }
 for (i=0;i<m;i++)
 {
  hashA1=(hashA1*p+a[i])%mod1;
  hashA2=(hashA2*p+a[i])%mod2;
  hash1=(hash1*p+b[i])%mod1;
  hash2=(hash2*p+b[i])%mod2;
  if (i)
  {
   p1=(p1*p)%mod1;
   p2=(p2*p)%mod2;
  }
 }
 if (hash1==hashA1&&hash2==hashA2)
 {
  mt[0]=1;
  nr++;
 }
 for (i=m;i<n;i++)
 {
  hash1=((hash1-(b[i-m]*p1)%mod1+mod1)*p+b[i])%mod1;
  hash2=((hash2-(b[i-m]*p2)%mod2+mod2)*p+b[i])%mod2;
  if (hash1==hashA1&&hash2==hashA2)
  {
   nr++;
   mt[i-m+1]=1;
  }
 }
 printf("%ld\n",nr);
 nr=0;
 for (i=0;i<n&&nr<1000;i++)
  if (mt[i])
  {
   nr++;
   printf("%ld ",i);
  }
 printf("\n");
 return 0;
}