Pagini recente » Cod sursa (job #1433451) | Cod sursa (job #1123919) | Cod sursa (job #1381439) | Cod sursa (job #964832) | Cod sursa (job #2767800)
#include <iostream>
#include <fstream>
#include <vector>
#define MOD 10009
#define HASH 3
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
int len_s1, len_s2, count = 0;
string s1, s2;
vector<long long> set[MOD];
long long hashFactor = 1;
bool setContains(long long hashVal) {
long long pos = hashVal % MOD;
for (int i = 0; i < set[pos].size(); i++) {
if (set[pos][i] == hashVal) {
return true;
}
}
return false;
}
void addWord(string s) {
long long hashVal = 0;
for (int i = 0; i < len_s2; i++) {
hashVal = hashVal * HASH + (s[i] - 'a');
}
if (!setContains(hashVal))
set[hashVal % MOD].push_back(hashVal);
}
int main() {
f >> s1;
f >> s2;
len_s1 = s1.length();
len_s2 = s2.length();
addWord(s2);
for (int i = 1; i < len_s2; i++) {
hashFactor = hashFactor * HASH;
}
while (f >> s2) {
addWord(s2);
}
long long hashVal = 0;
for (int i = 0; i < len_s2; i++) {
hashVal = hashVal * HASH + (s1[i] - 'a');
}
if (setContains(hashVal)) {
count++;
}
for (int i = len_s2; i < len_s1; i++) {
int prevVal = s1[i-len_s2] - 'a', val = s1[i] - 'a';
hashVal = (hashVal - (prevVal * hashFactor)) * HASH + val;
if (setContains(hashVal))
count++;
}
g << count;
return 0;
}