Pagini recente » Cod sursa (job #392737) | Cod sursa (job #3152730) | Cod sursa (job #2232832) | Cod sursa (job #2642464) | Cod sursa (job #2470322)
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include <string.h>
#include <fstream>
#include <iostream>
#define mod 5099
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
char s[10000005], c[25];
vector <unsigned int> Hash[mod];
int search(unsigned int val) {
int index = val % mod;
for(auto i : Hash[index]) {
if(i == val) return 1;
}
/*vector<unsigned int> v = Hash[index];
int len = v.size();
for(int i = 0; i < len; i++) {
if(v[i] == val)
return 1;
}*/
return 0;
}
int main() {
f >> s;
int len, nr = 0;
unsigned int pwr = 1;
unsigned int Hash_value;
while(f >> c) {
len = strlen(c);
Hash_value = 0;
for(int i = 0; i < len; i++) {
Hash_value = Hash_value * 3 + c[i] - 'a';
}
int idx = Hash_value % mod;
for(auto i : Hash[idx]) {
if(i == Hash_value)
continue;
}
Hash[Hash_value % mod].push_back(Hash_value);
}
for(int i = 0; i < len; i++) {
pwr *= 3;
}
int len_txt = strlen(s);
Hash_value = 0;
for(int i = 0; i < len_txt; i++) {
Hash_value = Hash_value * 3 + (s[i] - 'a');
if(i >= len) {
Hash_value = Hash_value - pwr * (s[i - len] - 'a');
}
if(i >= len - 1) {
nr += search(Hash_value);
}
}
g << nr;
return 0;
}