Pagini recente » Cod sursa (job #255749) | Cod sursa (job #251937) | Cod sursa (job #1853014) | Cod sursa (job #2001437) | Cod sursa (job #2295856)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("abc2.in");
ofstream fo("abc2.out");
const int MOD1 = 666013, MOD2 = 1 << 25, B = 250;
using i64 = long long;
using pii = pair<int, int>;
struct MUIE_TAMIO {
vector<int> hsh[MOD1];
void insert(int h1, int h2) {
hsh[h1].push_back(h2);
}
bool find(int h1, int h2) {
for (auto i: hsh[h1])
if (i == h2)
return true;
return false;
}
};
MUIE_TAMIO s;
string vsb, str;
int antwoord, len, n;
static pii get_hsh(const string &str) {
i64 h1 = 0, h2 = 0;
for (auto i: str) {
h1 = (h1 * B + i) % MOD1;
h2 = (h2 * B + i) % MOD2;
}
return pii(h1, h2);
}
static void fix(i64 &x, i64 &y) {
if (x < 0)
x+= MOD1;
if (y < 0)
y+= MOD2;
}
int main(){
i64 h1 = 0, h2 = 0, pwr1 = 1, pwr2 = 1;
fi >> vsb;
n = vsb.size();
while (fi >> str) {
auto tmp = get_hsh(str);
s.insert(tmp.first, tmp.second);
len = str.size();
}
for (int i = 0; i < len; ++i) {
h1 = (h1 * B + vsb[i]) % MOD1;
h2 = (h2 * B + vsb[i]) % MOD2;
if (i + 1 == len)
break;
pwr1 = pwr1 * B % MOD1;
pwr2 = pwr2 * B % MOD2;
}
antwoord+= int(s.find(h1, h2));
for (int i = 0; i + len < n; ++i) {
h1 = (h1 - pwr1 * vsb[i]) % MOD1;
h2 = (h2 - pwr2 * vsb[i]) % MOD2;
fix(h1, h2);
h1 = (h1 * B + vsb[i + len]) % MOD1;
h2 = (h2 * B + vsb[i + len]) % MOD2;
if (s.find(h1, h2))
antwoord+= 1;
}
fo << antwoord << endl;
cerr << antwoord << endl;
return 0;
}
/* Prostitutia
* nu este o recompensa adecvata codatului byat proola
*/