Pagini recente » Cod sursa (job #3355320) | Cod sursa (job #3349540) | Cod sursa (job #3347696) | Profil RaresH | Cod sursa (job #3318147)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 10000005;
const long long BASE1 = 131;
const long long MOD1 = 1000000007;
const long long BASE2 = 137;
const long long MOD2 = 1000000009;
const char HASHER = 'a' - 1;
char TEXT[NMAX], WORD[25];
long long powers1[25], powers2[25];
ifstream fin("abc2.in");
ofstream fout("abc2.out");
void PrecomputePowers(int L) {
powers1[0] = powers2[0] = 1;
for (int i = 1; i <= L; i++) {
powers1[i] = (powers1[i - 1] * BASE1) % MOD1;
powers2[i] = (powers2[i - 1] * BASE2) % MOD2;
}
}
pair<long long,long long> HashString(const char s[], int L) {
long long h1 = 0, h2 = 0;
for(int i = 0; i < L; i++){
h1 = (h1 * BASE1 + (s[i] - HASHER)) % MOD1;
h2 = (h2 * BASE2 + (s[i] - HASHER)) % MOD2;
}
return {h1,h2};
}
long long CombineHashes(pair<long long,long long> h){
return h.first * MOD2 + h.second;
}
unordered_set<long long> BuildDictionary(vector<string> &words, int L){
unordered_set<long long> dict;
for(auto &w: words){
if((int)w.size() != L) continue;
dict.insert(CombineHashes(HashString(w.c_str(),L)));
}
return dict;
}
pair<long long,long long> UpdateWindowHash(pair<long long,long long> h, char out, char in, int L){
h.first = (h.first - (out - HASHER) * powers1[L-1] % MOD1 + MOD1) % MOD1;
h.first = (h.first * BASE1 + (in - HASHER)) % MOD1;
h.second = (h.second - (out - HASHER) * powers2[L-1] % MOD2 + MOD2) % MOD2;
h.second = (h.second * BASE2 + (in - HASHER)) % MOD2;
return h;
}
long long CountPositions(char text[], int n, int L, unordered_set<long long> &dict){
pair<long long,long long> h = HashString(text,L);
long long combined = CombineHashes(h);
long long count = dict.count(combined) ? 1 : 0;
for(int i = L; i < n; i++){
h = UpdateWindowHash(h, text[i-L], text[i], L);
combined = CombineHashes(h);
if(dict.count(combined)) count++;
}
return count;
}
int main(){
ios::sync_with_stdio(false);
fin.tie(nullptr);
fin >> TEXT;
int n = strlen(TEXT);
vector<string> words;
while(fin >> WORD) words.push_back(string(WORD));
if(words.empty()){
fout << 0 << "\n";
return 0;
}
int L = words[0].size();
if(n < L){
fout << 0 << "\n";
return 0;
}
PrecomputePowers(L);
unordered_set<long long> dict = BuildDictionary(words,L);
long long result = CountPositions(TEXT,n,L,dict);
fout << result << "\n";
return 0;
}