Pagini recente » Cod sursa (job #2557353) | Cod sursa (job #2569717) | Cod sursa (job #2467732) | Cod sursa (job #1997342) | Cod sursa (job #2811753)
#include <iostream>
#include <fstream>
#include <vector>
#define MOD 30007
#define HASH 3
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
int lenS1, lenS2, count = 0;
string s1, s2;
vector<unsigned int> set[MOD];
unsigned int hashFactor = 1;
bool setContains(unsigned int hashVal) {
unsigned int key = hashVal % MOD;
for (int i = 0; i < set[key].size(); i++) {
if (set[key][i] == hashVal) {
return true;
}
}
return false;
}
void addWord(string s) {
unsigned int hashVal = 0;
for (int i = 0; i < lenS2; i++) {
hashVal = hashVal * HASH + (s[i] - 'a');
}
if (!setContains(hashVal)) {
unsigned int key = hashVal % MOD;
set[key].push_back(hashVal);
}
}
int main() {
f >> s1;
lenS1 = s1.length();
while (f >> s2) {
lenS2 = s2.length();
addWord(s2);
}
for (int i = 1; i < lenS2; i++) {
hashFactor = hashFactor * HASH;
}
unsigned int hashVal = 0;
for (int i = 0; i < lenS2; i++) {
hashVal = hashVal * HASH + (s1[i] - 'a');
}
if (setContains(hashVal)) {
count++;
}
for (int i = lenS2; i < lenS1; i++) {
int prevVal = s1[i-lenS2] - 'a', val = s1[i] - 'a';
hashVal = (hashVal - (prevVal * hashFactor)) * HASH + val;
if (setContains(hashVal))
count++;
}
g << count;
return 0;
}