Pagini recente » Cod sursa (job #1359695) | Cod sursa (job #857901) | Cod sursa (job #2588038) | Cod sursa (job #717776) | Cod sursa (job #1970945)
#include <stdint.h>
#include <fstream>
#include <string.h>
#define nmax 10000001
#define nrmaxcuv 50001
#define mmax 21
#define mod 666013
using namespace std;
fstream f1("abc2.in", ios::in);
fstream f2("abc2.out", ios::out);
char sir[nmax], cuv[mmax];
int32_t n, nrt, t[nrmaxcuv], rez;
int16_t m;
const int16_t d=3;
int32_t ct;///=d^(m-1)
int32_t hash_c()
{
int16_t i;
int32_t h=0;
for(i=0; i<m; i++)
{
h=h*d+(cuv[i]-'a'+1);
h%=mod;
}
return h;
}
int32_t hash_s()
{
int16_t i;
int32_t h=0;
for(i=0; i<m; i++)
{
h=h*d+(sir[i]-'a'+1);
h%=mod;
}
return h;
}
void putere()
{
int16_t i;
ct=1;
for(i=1; i<m; i++)
{
ct*=d;
ct%=mod;
}
}
void adauga(int32_t st, int32_t dr, int32_t val)
{
if(st<=dr)
{
int32_t mijl=(st+dr)/2;
if(val==t[mijl]) ;
else if(val< t[mijl]) adauga(st, mijl-1, val);
else adauga(mijl+1, dr, val);
}
else
{
///adaugi in locul poz st valoarea val
int32_t i;
for(i=nrt; i>=st; i--)
t[i+1]=t[i];
t[st]=val;
nrt++;
}
}
int32_t find_c(int32_t st, int32_t dr, int32_t val)
{
if(st<=dr)
{
int32_t mijl=(st+dr)/2;
if(t[mijl]==val) return 1;
else if(t[mijl]<val) return find_c(mijl+1, dr, val);
else return find_c(st, mijl-1, val);
}
else return 0;
}
int main()
{
int32_t val, i;
f1>>sir; n=strlen(sir);
f1>>cuv; m=strlen(cuv);
do
{
val=hash_c();
adauga(1, nrt, val);///adaugi cu cautare biara val cuv curent daca nu exista in t
}while(f1>>cuv);
val=hash_s();
rez+=find_c(1, nrt, val);///cauti nr coresp primei secv in vectorul t de dimensiune nr(cautare binara)
putere();///calc ct, care te ajuta sa faci trecerea intre secv textului lung
for(i=1; i<=n; i++)
{
///treci la urmatoarea secv modificand hashul pt val
val=(val- ct*(sir[i-1]-'a'+1)+ d*mod) %mod;
val= (val*d+ sir[i+m-1]-'a'+1)%mod;
rez+=find_c(1, nrt, val);
}
f2<<rez;
return 0;
}