Pagini recente » Istoria paginii utilizator/uvt_butunoi_cartis_cheroiu-cozma | Istoria paginii runda/temadec2019/clasament | Autentificare | Istoria paginii runda/oni_mixed/clasament | Cod sursa (job #1013079)
#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 int P = 3;
vector<int> h[MOD1];
int n;
string bigString, a;
bool found (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');
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;
}