Pagini recente » Cod sursa (job #3342564) | Cod sursa (job #1020097) | Cod sursa (job #3314103) | Cod sursa (job #2211347) | Cod sursa (job #3318140)
#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 RabinKarp(const char pattern[], const char text[]) {
int n = strlen(pattern);
int m = strlen(text);
if (n > m) return 0;
long long hash_pattern = HashEntireString(pattern, n);
long long hash_text = HashEntireString(text, n);
int count = 0;
if (hash_pattern == hash_text) count++;
for (int i = n; i < m; i++) {
hash_text = (hash_text - (text[i - n] - HASHER) * powers[n - 1]) % MOD;
if (hash_text < 0) hash_text += MOD;
hash_text = (hash_text * BASE + (text[i] - HASHER)) % MOD;
if (hash_text == hash_pattern) count++;
}
return count;
}
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()) {
fout << 0;
return 0;
}
int L = cuvinte[0].size();
PrecomputePowers(L);
unordered_set<string> unice;
for (auto &w : cuvinte)
if ((int)w.size() == L)
unice.insert(w);
long long total = 0;
for (auto &cuv : unice)
total += RabinKarp(cuv.c_str(), A);
fout << total << "\n";
return 0;
}