Cod sursa(job #2107098)

Utilizator AnduRazvanMindrescu Andu AnduRazvan Data 16 ianuarie 2018 19:10:39
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <cstring>
#include <stdlib.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
char s[10000005];
#define prim 666017
char cuv[22];
int main()
{ fin>>s;
  fin>>cuv;
  unsigned int nr=0,i,n=strlen(s),nc=strlen(cuv),putere=1,j;
   for(i=0;i<nc;i++)
   { nr+=(cuv[i]-'a')*putere;
     putere*=3;
   }
   unsigned int loc=nr%prim;
   unsigned int **h=(unsigned int **) malloc(prim*sizeof(unsigned int*));
   unsigned int *ap=(unsigned int*)calloc(prim,sizeof(unsigned int));
    ap[loc]++;
    h[loc]=(unsigned int*)realloc(h[loc],ap[loc]*sizeof(unsigned int));
    h[loc][ap[loc]-1]=nr;
  while(fin>>cuv)
  { nr=0,putere=1;
      for(i=0;i<nc;i++)
    { nr+=(cuv[i]-'a')*putere;
     putere*=3;
    }
     loc=nr%prim;
     ap[loc]++;
     h[loc]=(unsigned int*)realloc(h[loc],ap[loc]*sizeof(unsigned int));
     h[loc][ap[loc]-1]=nr;
  }
int sol=0;
nr=0,putere=1;
      for(i=0;i<nc;i++)
    { nr+=(s[i]-'a')*putere;
     putere*=3;
    }
    putere/=3;
     loc=nr%prim;
     for(i=0;i<ap[loc];i++)
       if(h[loc][i]==nr) {sol++;break;}
     for(i=nc;i<n;i++)
      {nr-=s[i-nc]-'a';
       nr/=3;
       nr+=(s[i]-'a')*putere;
              loc=nr%prim;
     for(j=0;j<ap[loc];j++)
       if(h[loc][j]==nr) {sol++;break;}
      }
      fout<<sol;
    return 0;
}