Cod sursa(job #151998)

Utilizator AlxCojocaru Alexandru Alx Data 8 martie 2008 21:27:46
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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",stdout);
 freopen("strmatch.out","w",stdout);
 scanf("%s\n%s\n",&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+a[i]*p)%mod1;
  hashA2=(hashA2+a[i]*p)%mod2;
  hash1=(hash1+b[i]*p)%mod1;
  hash2=(hash2+b[i]*p)%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)+b[i]*p)%mod1;
  hash2=((hash2-(b[i-m]*p2)%mod2+mod2)+b[i]*p)%mod2;
  if (hash1==hashA1&&hash2==hashA2)
  {
   nr++;
   mt[i-m+1]=1;
  }
 }
 printf("%ld\n",nr);
 nr=0;
 for (i=0;i<m&&nr<1000;i++)
  if (mt[i])
  {
   nr++;
   printf("%ld ",i);
  }
 return 0;
}