Pagini recente » Cod sursa (job #436219) | Cod sursa (job #1028930) | Cod sursa (job #2519493) | Cod sursa (job #2113194) | Cod sursa (job #2768652)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
string s, aux;
unsigned int base;
int l, l2;
const int MOD = 10003;
vector <unsigned int> mp[MOD];
inline bool exista(unsigned int x) {
unsigned int key = x % MOD;
for (int i = 0; i < mp[key].size(); ++i)
if (mp[key][i] == x ) return 1;
return 0;
}
inline void push(unsigned int x){
if (!exista(x)) {
unsigned int key = x % MOD;
mp[key].push_back(x);
}
}
void read() {
int i, j;
unsigned int hash;
ifstream f("abc2.in");
f >> s;
while (f >> aux) {
hash = 0;
base = 1;
for (j = 0; j < aux.size(); j++)
hash = hash * 3 + (aux[j] - 'a');
l2 = aux.size();
push(hash);
}
}
int nr;
void solve() {
int i;
unsigned int hash = 0;
for (i = 0; i < l2; i++) {
hash = hash * 3 + (s[i] - 'a');
base = base * 3;
}
base /= 3;
if (exista(hash))
nr++;
for (i = l2; i < s.size(); i++) {
hash = (hash - (s[i - l2] - 'a') * base) * 3 + (s[i] - 'a');
if (exista(hash))
nr++;
}
}
void output() {
ofstream g("abc2.out");
g << nr;
g.close();
}
int main() {
read();
solve();
output();
return 0;
}