Pagini recente » Borderou de evaluare (job #1596291) | Cod sursa (job #3311642) | Monitorul de evaluare | Cod sursa (job #201866) | Cod sursa (job #656134)
Cod sursa(job #656134)
#include<fstream>
#include<cstring>
#include<algorithm>
using namespace std;
#define SMAX 10000010
#define NMAX 50010
#define CMAX 25
#define PUTERE 101
#define PRIM1 100003
#define PRIM2 100019
typedef struct hashh
{
int unu,doi;
} hashh;
int n=-1;
hashh hashc[NMAX];
char s[SMAX];
int lungs,lungc;
int hashscurentunu,hashscurentdoi;
int pozitiicandidat;
bool comp (hashh a, hashh b)
{
if (a.unu = b.unu)
return a.doi < b.doi; else
return a.unu < b.unu;
}
void cauta(int st, int dr)
{
int mijl = (st + dr) / 2;
if (st <= dr)
{
if (hashscurentunu == hashc[mijl].unu && hashscurentdoi == hashc[mijl].doi)
pozitiicandidat++; else
if ((hashscurentunu == hashc[mijl].unu && hashscurentdoi < hashc[mijl].doi) || hashscurentunu < hashc[mijl].unu)
cauta(st, mijl-1); else
cauta(mijl+1, dr);
}
}
void solve()
{
int i,puteremax1=1,puteremax2=1;
for (i=0; i<lungc; ++i)
{
hashscurentunu = (hashscurentunu * PUTERE + s[i]) % PRIM1;
hashscurentdoi = (hashscurentdoi * PUTERE + s[i]) % PRIM2;
if (i > 0)
{
puteremax1 = (puteremax1 * PUTERE) % PRIM1;
puteremax2 = (puteremax2 * PUTERE) % PRIM2;
}
}
for (i=0; i<=lungs - lungc; ++i)
{
if (i > 0)
{
hashscurentunu = ((hashscurentunu - (s[i-1] * puteremax1) % PRIM1 + PRIM1) * PUTERE + s[i + lungc - 1]) % PRIM1;
hashscurentdoi = ((hashscurentdoi - (s[i-1] * puteremax2) % PRIM2 + PRIM2) * PUTERE + s[i + lungc - 1]) % PRIM2;
}
cauta(0, n);
}
}
void read()
{
int i;
char c[CMAX];
ifstream fin("abc2.in");
fin.get(s, SMAX); fin.get();
lungs = (int)strlen(s);
while ( !fin.eof() )
{
fin.get(c, CMAX); fin.get();
++n;
for (i=0; i<(int)strlen(c); ++i)
{
hashc[n].unu = (hashc[n].unu * PUTERE + c[i]) % PRIM1;
hashc[n].doi = (hashc[n].doi * PUTERE + c[i]) % PRIM2;
}
}
lungc = (int)strlen(c);
}
void write()
{
ofstream fout("abc2.out");
fout<<pozitiicandidat<<'\n';
fout.close();
}
int main()
{
read();
sort(hashc, hashc+n+1, comp);
solve();
write();
return 0;
}