Pagini recente » Cod sursa (job #2135883) | Cod sursa (job #1243363) | Cod sursa (job #1190947) | Cod sursa (job #1059239) | Cod sursa (job #860638)
Cod sursa(job #860638)
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#define mod 100007
#define Hmod1 666013
#define Hmod2 100021
using namespace std;
vector<int> H[mod];
char text[10000000];
void add(int x)
{
const int m = x%mod;
vector<int>::iterator i=H[m].begin(), stop=H[m].end();
while (i != stop)
{
if (*i == x)
return;
++i;
}
H[m].push_back(x);
}
short search(int x)
{
const int m = x%mod;
vector<int>::iterator i=H[m].begin(), stop=H[m].end();
while (i != stop)
{
if (*i == x)
return 1;
++i;
}
return 0;
}
int hash1(char *cuv, int l)
{
int val=0, i;
for (i=0; i<l; ++i)
val = (val*3 + cuv[i]-'a')%Hmod1;
return val;
}
int hash2(char *cuv, int l)
{
int val=0, i;
for (i=0; i<l; ++i)
val = (val*3 + cuv[i]-'a')%Hmod2;
return val;
}
int main()
{
ifstream in("abc2.in"); ofstream out("abc2.out");
char cuv[20];
int i, l, cnt=0, val1, val2, n, g1=1, g2=1;
in>>text>>cuv;
l = strlen(cuv);
add(hash1(cuv, l)); add(hash2(cuv, l));
while (in>>cuv)
{
add(hash1(cuv, l));
add(hash2(cuv, l));
}
for (i=1; i<l; ++i)
{
g1 = (g1*3)%Hmod1;
g2 = (g2*3)%Hmod2;
}
val1=hash1(text, l); val2=hash2(text, l);
cnt += (search(val1) && search(val2));
n = strlen(text);
for (i=l; i<n; ++i)
{
val1 = ((val1 - ((text[i-l]-'a')*g1)%Hmod1 + Hmod1)*3 + text[i]-'a')%Hmod1;
val2 = ((val2 - ((text[i-l]-'a')*g2)%Hmod2 + Hmod2)*3 + text[i]-'a')%Hmod2;
cnt += (search(val1) && search(val2));
}
out<<cnt;
return 0;
}