Pagini recente » Cod sursa (job #3342906) | Cod sursa (job #145707) | Cod sursa (job #3350864) | Cod sursa (job #3350487) | Cod sursa (job #3318142)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 10000005;
const long long BASE = 131;
const long long MOD = 1000000007;
const char HASHER = 'a' - 1;
char A[NMAX], B[25];
long long powers[25];
ifstream fin("abc2.in");
ofstream fout("abc2.out");
void PrecomputePowers(int n) {
powers[0] = 1;
for (int i = 1; i <= n; i++)
powers[i] = (powers[i - 1] * BASE) % MOD;
}
long long HashEntireString(const char s[], int n) {
long long h = 0;
for (int i = 0; i < n; i++)
h = (h * BASE + (s[i] - HASHER)) % MOD;
return h;
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
fin >> A;
int n = strlen(A);
vector<string> cuvinte;
while (fin >> B)
cuvinte.push_back(string(B));
if (cuvinte.empty() || n == 0) {
fout << 0 << "\n";
return 0;
}
int L = cuvinte[0].size();
if (n < L) {
fout << 0 << "\n";
return 0;
}
PrecomputePowers(L);
unordered_set<long long> dict;
dict.reserve(cuvinte.size() * 2);
for (auto &w : cuvinte)
if ((int)w.size() == L)
dict.insert(HashEntireString(w.c_str(), L));
long long current_hash = HashEntireString(A, L);
long long count = 0;
if (dict.find(current_hash) != dict.end())
count++;
for (int i = L; i < n; i++) {
current_hash = (current_hash - (A[i - L] - HASHER) * powers[L - 1]) % MOD;
if (current_hash < 0) current_hash += MOD;
current_hash = (current_hash * BASE + (A[i] - HASHER)) % MOD;
if (dict.find(current_hash) != dict.end())
count++;
}
fout << count << "\n";
return 0;
}