Cod sursa(job #1616979)

Utilizator nnnmmmcioltan alex nnnmmm Data 27 februarie 2016 12:21:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<cstring>
const int NMAX=2000010;
char A[NMAX],B[NMAX];
const int MOD1=666013,MOD2=100021;
int rasp[NMAX],nr_rasp;
int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 gets(A+1);
 gets(B+1);
 int n=strlen(A+1),m=strlen(B+1);
 int Ahash1=0,Ahash2=0;
 int put1=1,put2=1;
 for(int i=1;i<=n;i++)
     {
      Ahash1=(73*Ahash1+A[i])%MOD1;
      Ahash2=(73*Ahash2+A[i])%MOD2;
      if(i>1)
         {
          put1*=73;
          put1%=MOD1;
          put2*=73;
          put2%=MOD2;
         }
     }
 //printf("%d\n%d\n",Ahash1,Ahash2);
 int Bhash1=0,Bhash2=0;
 for(int i=1;i<=n;i++)
     {
      Bhash1=(73*Bhash1+B[i])%MOD1;
      Bhash2=(73*Bhash2+B[i])%MOD2;
     }
 //printf("%d\n%d\n",Bhash1,Bhash2);
 if(Bhash1==Ahash1 && Bhash2==Ahash2)
    {
     if(nr_rasp<1000)
        rasp[++nr_rasp]=0;
     else
        ++nr_rasp;
    }
 for(int i=n+1;i<=m;i++)
     {
      Bhash1=((Bhash1-(put1*B[i-n])%MOD1+MOD1)*73+B[i])%MOD1;
      Bhash2=((Bhash2-(put2*B[i-n])%MOD2+MOD2)*73+B[i])%MOD2;
      if(Bhash1==Ahash1 && Bhash2==Ahash2)
         {
          if(nr_rasp<1000)
             rasp[++nr_rasp]=i-n;
          else
             ++nr_rasp;
         }
     }
 printf("%d\n",nr_rasp);
 for(int i=1;i<=nr_rasp && i<=1000;i++)
     printf("%d ",rasp[i]);
 return 0;
}