Pagini recente » Cod sursa (job #1431112) | Cod sursa (job #426561) | Cod sursa (job #1618967) | Cod sursa (job #174435) | Cod sursa (job #2107119)
#include <fstream>
#include <cstring>
#include <stdlib.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
char s[10000005];
#define prim 9983
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;
}