Pagini recente » Cod sursa (job #46648) | Cod sursa (job #2096254) | Cod sursa (job #2826956) | Cod sursa (job #1184094) | Cod sursa (job #2768643)
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;
string s, aux;
long long v[50001], l;
long long base;
int l2;
void read() {
int i, j;
long long hash;
ifstream f("abc2.in");
f >> s;
while (f >> aux) {
hash = 0;
base = 1;
for (j = 0; j < aux.size(); j++) {
hash = hash * 3 + (aux[j] - 'a');
base = base * 3;
}
base /= 3;
l2 = aux.size();
v[++l] = hash;
}
}
int nr;
void solve() {
int i, st, dr, mij;
sort(v + 1, v + l + 1);
long long hash = 0;
for (i = 0; i < l2; i++)
hash = hash * 3 + (s[i] - 'a');
st = 1, dr = l;
while (st <= dr) {
mij = (st + dr) / 2;
if (v[mij] == hash) {
nr++;
break;
}
if (v[mij] < hash)
st = mij + 1;
else dr = mij - 1;
}
for (i = l2; i < s.size(); i++) {
hash = (hash - (s[i - l2] - 'a') * base) * 3 + (s[i] - 'a');
st = 1, dr = l;
while (st <= dr) {
mij = (st + dr) / 2;
if (v[mij] == hash) {
nr++;
break;
}
if (v[mij] < hash)
st = mij + 1;
else dr = mij - 1;
}
}
}
void output() {
ofstream g("abc2.out");
g << nr;
g.close();
}
int main() {
read();
solve();
output();
return 0;
}