Pagini recente » Cod sursa (job #3183864) | Cod sursa (job #1799605) | Cod sursa (job #3290250) | Cod sursa (job #2523769) | Cod sursa (job #1054350)
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef vector<unsigned> ht;
typedef ht::iterator it;
const unsigned MOD = 99991;
string text, word;
ht h[MOD + 2];
unsigned pow(unsigned exp) {
if (exp > 0) return 3u * pow(exp - 1u);
else return 1;
}
bool find(unsigned val){
bool ok = 0;
for(it i = h[val % MOD].begin(); i != h[val % MOD].end() && !ok; i++)
ok = (*i == val);
return ok;
}
int main() {
ifstream f("abc2.in");
ofstream g("abc2.out");
f >> text >> word;
unsigned nr = 0, n = word.size(), val, maxpow = pow(n - 1);
do {
val = 0;
for (int i = 0; i < word.size(); i++)
val = val * 3u + (word[i] - 'a');
h[val % MOD].push_back(val);
f >> word;
} while (!f.eof());
for (int i = 0; i < n; i++)
val = val * 3u + text[i] - 'a';
nr += find(val);
for (int i = n; i < text.size(); i++) {
val -= maxpow * (text[i - n] - 'a');
val = val * 3u + text[i] - 'a';
nr += find(val);
}
g << nr;
f.close();
g.close();
return 0;
}