Mai intai trebuie sa te autentifici.
Cod sursa(job #2443232)
Utilizator | Data | 26 iulie 2019 23:53:13 | |
---|---|---|---|
Problema | Abc2 | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.06 kb |
#include <bits/stdc++.h>
#include <string.h>
#include <fstream>
#include <iostream>
#define mod 29989
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;
vector<unsigned int> v = Hash[index];
for(int i = 0; i < v.size(); 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';
}
Hash[Hash_value % mod].push_back(Hash_value);
}
for(int i = 0; i < len; i++) {
pwr = 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;
}