Cod sursa(job #2106914)

Utilizator AnduRazvanMindrescu Andu AnduRazvan Data 16 ianuarie 2018 15:19:44
Problema Abc2 Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define prim 666013
long long Putere(long long x,long long y)
{ long long p=1;
  int i;
   for(i=1;i<=y;i++)
   p=p*x;
    return p;
}
int main()
{  FILE *f=fopen("abc2.in","r");
   FILE *g=fopen("abc2.out","w");
   char *s,*c;
   s=(char*)malloc(10000000*sizeof(char));
   c=(char*)malloc(20*sizeof(char));
   fgets(s,10000000,f);//fgetc(f);
   fgets(c,20,f);//fgetc(f);
   long long i,j;
   long long **h=(long long **)malloc(prim*sizeof(long long*));
   long long *ap=(long long*)calloc(prim,sizeof(long long));
   long long loc,n=strlen(s),nc=strlen(c),nr=0;
   n--;nc--;
   for(i=0;i<nc;i++)
     nr=nr+(s[i]-('a'-1))*Putere(3,i);
    loc=nr%prim;
    ap[loc]++;
    h[loc]=realloc(h[loc],ap[loc]*sizeof(long long));
    h[loc][ap[loc]-1]=nr;
   for(i=nc;i<n;i++)
    {nr-=s[i-nc]-('a'-1);
     nr/=3;
     nr+=(s[i]-('a'-1))*Putere(3,nc-1);
     loc=nr%prim;
     ap[loc]++;
     h[loc]=realloc(h[loc],ap[loc]*sizeof(long long));
     h[loc][ap[loc]-1]=nr;
    }
   int sol=0,k;
    while(c[0]!='\n')
    {nr=0;
     for(i=0;i<nc;i++)
      {nr+=(c[i]-('a'-1))*Putere(3,i);}
       loc=nr%prim;
       for(j=0;j<ap[loc];j++)
        if (h[loc][j]==nr)
        {   h[loc][j]=h[loc][ap[loc]-1];
            ap[loc]--;

            sol++;

        }
     fgets(c,22,f);//fgetc(f);
    }


    fprintf(g,"%ld",sol);
    return 0;
}