Cod sursa(job #155670)

Utilizator lucicanuAndrei-Lucian Croitoru lucicanu Data 12 martie 2008 07:29:32
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<stdio.h>
#include<string.h>

#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021

char A[MAXN], B[MAXN];
int NA, NB;

int hashA1, hashA2, P1, P2;

char match[MAXN];

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",A,B);
NA=strlen(A);
NB=strlen(B);
P1=P2=1;
hashA1=hashA2=0;
for (int i=0;i<NA;i++)
   {
   hashA1=(hashA1*P+A[i])%MOD1;
   hashA2=(hashA2*P+A[i])%MOD2;
   if (i!=0)
     {
     P1=(P1*P)%MOD1;
     P2=(P2*P)%MOD2;
     }
   }
if (NA>NB)
  {
  printf("0\n");
  return 0;
  }
int hash1=0, hash2=0;
for (int i=0;i<NA;i++)
   {
   hash1=(hash1*P+B[i])%MOD1;
   hash2=(hash2*P+B[i])%MOD2;
   }
int Nr=0;
if (hash1==hashA1 && hash2==hashA2)
  {
  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==hashA1 && hash2==hashA2)
     {
     match[i-NA+1]=1;
     Nr++;
     }
   }
printf("%d\n",Nr);
Nr=0;
for (i=0;i<NB;i++)
   if (match[i])
     {
     Nr++;
     printf("%d ",i);
     }
printf("\n");
return 0;
}