Pagini recente » Cod sursa (job #2268000) | Cod sursa (job #3341482) | Cod sursa (job #967748) | Cod sursa (job #3299211) | Cod sursa (job #3303082)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int getHash(string &str) {
int hsh = 0;
for (int i = 0; i < str.size(); i++) {
hsh = 3 * hsh + str[i] - 'a';
}
return hsh;
}
bool find(int val, vector <int> &v) {
int ans = -1;
for (int i = (1 << 15); i; i >>= 1) {
if (ans + i < v.size() && v[ans + i] <= val) {
ans += i;
}
}
return ans != -1 && v[ans] == val;
}
void solve() {
string str, s;
cin >> str;
vector <int> v;
int n;
while (cin >> s) {
n = s.size();
v.push_back(getHash(s));
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int hsh = 0, p = 1, ans = 0;
for (int i = 1; i < n; p *= 3, i++);
for (int i = 0; i < str.size(); i++) {
hsh = 3LL * hsh + str[i] - 'a';
if (i + 1 >= n) {
ans += find(hsh, v);
hsh = hsh - (str[i - n + 1] - 'a') * p;
}
}
cout << ans;
}
signed main() {
#ifdef LOCAL
assert(freopen("test.in", "r", stdin));
assert(freopen("test.out", "w", stdout));
#else
assert(freopen("abc2.in", "r", stdin));
assert(freopen("abc2.out", "w", stdout));
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int nrt = 1;
//cin >> nrt;
while (nrt--) {
solve();
}
return 0;
}