Pagini recente » Cod sursa (job #3156396) | Cod sursa (job #1482983) | Cod sursa (job #417955) | Cod sursa (job #2121837) | Cod sursa (job #2802232)
#include <bits/stdc++.h>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
using ll = long long;
const int MOD = 666013;
struct Hash {
vector<vector<int>> h;
Hash() : h(MOD, vector<int>{}) {}
void insert(string &s) {
int x = 0, p = 1, sum = 0;
for (int i = 0; i < (int)s.size(); i++) {
x = (ll)(x * 37 + s[i]) % MOD;
if (i > 0 && i != (int)s.size() - 1)
p = (ll)(p * 37) % MOD;
sum += s[i];
}
// cerr << "{" << x << ", " << sum << "}\n";
h[x].push_back(sum);
}
bool find(int x, int s) {
for (int val : h[x])
if (val == s)
return true;
return false;
}
};
int main() {
ios_base::sync_with_stdio(false);
in.tie(NULL);
out.tie(NULL);
string s; in >> s;
vector<int> v;
Hash H;
int l = 0;
string c; while (in >> c) {
H.insert(c);
l = (int)c.size();
}
int sum = 0, p = 1, x = 0;
for (int i = 0; i < l; i++) {
x = (ll)(x * 37 + s[i]) % MOD;
if (i > 0) {
p = (ll)(p * 37) % MOD;
}
sum += s[i];
}
// cerr << "\n\n";
// cerr << "{" << x << ", " << sum << "}\n";
int ans = 0;
if (H.find(x, sum))
ans++;
for (int i = l; i < (int)s.size(); i++) {
sum += -s[i - l] + s[i];
x = ((((ll)x - (p * s[i - l] % MOD) + MOD)) % MOD * 37 + s[i]) % MOD;
if (H.find(x, sum))
ans++;
// cerr << "{" << x << ", " << sum << "}\n";
}
out << ans << "\n";
return 0;
}