Pagini recente » Cod sursa (job #2787918) | Cod sursa (job #1951918) | Cod sursa (job #2271549) | Cod sursa (job #450751) | Cod sursa (job #1857667)
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
using namespace std;
const string name = "abc2",
in_file = name + ".in",
out_file = name + ".out";
ifstream fin(in_file);
ofstream fout(out_file);
const int MOD = 1e5 + 3;
vector<unsigned> hash_table[MOD];
string str;
unsigned length_word;
unsigned power3[21];
int hash_function(unsigned number) {
return number % MOD;
}
void add(unsigned key) {
int vaca = hash_function(key);
for (unsigned number : hash_table[vaca]) {
if (number == key) {
return;
}
}
hash_table[vaca].pb(key);
}
bool contains(unsigned key) {
int vaca = hash_function(key);
for (unsigned number : hash_table[vaca]) {
if (number == key) {
return true;
}
}
return false;
}
unsigned add_letter(unsigned nr, unsigned digit) {
// unsigned temp = nr / power3[length_word - 1];
unsigned temp = 1;
nr -= temp * power3[length_word - 1];
nr *= 3;
nr += digit;
return nr;
}
void process_word(string& word) {
unsigned current_number = 0;
for (unsigned i = 0; i < length_word; i++) {
current_number = add_letter(current_number, word[i] - 'a');
}
add(current_number);
}
int main() {
fin >> str;
power3[0] = 1;
for (int i = 1; i <= 20; i++) {
power3[i] = 3 * power3[i - 1];
}
string word;
while (fin >> word) {
if (!length_word) {
length_word = word.size();
if (length_word > str.size()) {
fout << 0;
return 0;
}
}
process_word(word);
}
int sol = 0;
unsigned current_number = 0;
for (unsigned i = 0; i < str.size(); i++) {
current_number = add_letter(current_number, str[i] - 'a');
if (length_word <= i + 1) {
if (contains(current_number)) {
sol++;
}
}
}
fout << sol;
return 0;
}