Pagini recente » Cod sursa (job #1320332) | Cod sursa (job #1739155) | Cod sursa (job #325217) | Cod sursa (job #2906140) | Cod sursa (job #860642)
Cod sursa(job #860642)
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#define mod1 100007
#define mod2 333337
#define Hmod 666013
using namespace std;
vector<int> H1[mod1], H2[mod2];
char text[10000000];
void add1(int x)
{
const int m = x%mod1;
vector<int>::iterator i=H1[m].begin(), stop=H1[m].end();
while (i != stop)
{
if (*i == x)
return;
++i;
}
H1[m].push_back(x);
}
void add2(int x)
{
const int m = x%mod2;
vector<int>::iterator i=H2[m].begin(), stop=H2[m].end();
while (i != stop)
{
if (*i == x)
return;
++i;
}
H2[m].push_back(x);
}
short search1(int x)
{
const int m = x%mod1;
vector<int>::iterator i=H1[m].begin(), stop=H1[m].end();
while (i != stop)
{
if (*i == x)
return 1;
++i;
}
return 0;
}
short search2(int x)
{
const int m = x%mod2;
vector<int>::iterator i=H2[m].begin(), stop=H2[m].end();
while (i != stop)
{
if (*i == x)
return 1;
++i;
}
return 0;
}
int hash(char *cuv, int l)
{
int val=0, i;
for (i=0; i<l; ++i)
val = (val*3 + cuv[i]-'a')%Hmod;
return val;
}
int main()
{
ifstream in("abc2.in"); ofstream out("abc2.out");
char cuv[20];
int i, l, cnt=0, val, n, g=1;
in>>text>>cuv;
l = strlen(cuv);
val = hash(cuv, l);
add1(val); add2(val);
while (in>>cuv)
{
val = hash(cuv, l);
add1(val); add2(val);
}
for (i=1; i<l; ++i)
g = (g*3)%Hmod;
val = hash(text, l);
cnt += (search1(val) && search2(val));
n = strlen(text);
for (i=l; i<n; ++i)
{
val = ((val - ((text[i-l]-'a')*g)%Hmod + Hmod)*3 + text[i]-'a')%Hmod;
cnt += (search1(val) && search2(val));
}
out<<cnt;
return 0;
}