Pagini recente » Cod sursa (job #1186775) | Cod sursa (job #2905263) | Cod sursa (job #519033) | Cod sursa (job #1239434) | Cod sursa (job #1013081)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int MOD1 = 67891;
const unsigned int P = 3;
vector<unsigned int> h[MOD1];
int n;
string bigString, a;
bool found (unsigned int hash1) {
for (int i = 0; i < h[hash1 % MOD1].size(); ++i)
if (h[hash1 % MOD1][i] == hash1)
return 1;
return 0;
}
int main() {
fin >> bigString;
while (fin >> a) {
unsigned int hash1 = 0;
n = a.size();
for (int i = 0; i < a.size(); ++i)
hash1 = (hash1 * P + a[i] - 'a');
h[hash1 % MOD1].push_back(hash1);
}
unsigned int curHash1 = 0;
for (int i = 0; i < n; ++i)
curHash1 = (curHash1 * P + bigString[i] - 'a');
unsigned int rez = 0, P1 = 1;
for (int i = 1; i < n; ++i)
P1 = (P1 * P) % MOD1;
if (found(curHash1))
++rez;
for (int i = n; i < bigString.size(); ++i) {
curHash1 -= P1 * (bigString[i - n] - 'a');
curHash1 = curHash1 * P + bigString[i] - 'a';
if (found(curHash1))
++rez;
}
fout << rez;
return 0;
}