Pagini recente » Cod sursa (job #1326949) | Cod sursa (job #1082053) | Cod sursa (job #1584847) | Cod sursa (job #848709) | Cod sursa (job #2296766)
#include <fstream>
#include <unordered_map>
#include <string>
#include <iostream>
#define M 1000000
using namespace std;
string s, x;
unordered_map<unsigned int, bool> dictionar;
int hashtable[M];
bool inside(int value) {
int v = value;
while (hashtable[value] != 0) {
if (hashtable[value] == v) {
return true;
}
value++;
if (value == M) { value = 0; }
}
return false;
}
void insert(int value) {
int v = value;
while (hashtable[value] != 0 and hashtable[value] != v) {
value++;
if (value == M) { value = 0; }
}
hashtable[value] = v;
}
int main(){
ifstream cin("abc2.in");
ofstream cout("abc2.out");
cin >> s;
while(cin >> x){
unsigned int cod = 0;
for(int i = 0; i < x.size(); i++)
cod = cod * 3 + x[i] - 'a';
// cout << cod << endl;
insert(cod % M);
}
int n = x.size();
unsigned int p3lan = 1;
for(int i = 1; i < n; i++)
p3lan *= 3;
unsigned int cod = 0;
int ans = 0;
for(int i = 0, j = 0; i <= s.size() - n; i++){
while(j < s.size() && j < i + n){
cod = cod * 3 + s[j] - 'a';
// cout << cod << endl;
j++;
}
if (inside(cod % M))
ans ++;
// cout << cod << endl;
cod -= p3lan * (s[i] - 'a');
}
cout << ans << endl;
return 0;
}