Pagini recente » Cod sursa (job #671131) | Autentificare | Cod sursa (job #206591) | Cod sursa (job #713693) | Cod sursa (job #1013067)
#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 MOD2 = 1045279;
const int P = 27;
vector<int> h[MOD1];
int n;
string bigString, a;
bool found (int hash1, int hash2) {
for (int i = 0; i < h[hash1].size(); ++i)
if (h[hash1][i] == hash2)
return 1;
return 0;
}
int main() {
fin >> bigString;
while (fin >> a) {
int hash1 = 0, hash2 = 0;
n = a.size();
for (int i = 0; i < a.size(); ++i) {
hash1 = (hash1 * P + a[i]) % MOD1;
hash2 = (hash2 * P + a[i]) % MOD2;
}
h[hash1].push_back(hash2);
}
int curHash1 = 0, curHash2 = 0;
for (int i = 0; i < n; ++i) {
curHash1 = (curHash1 * P + bigString[i]) % MOD1;
curHash2 = (curHash2 * P + bigString[i]) % MOD2;
}
int rez = 0;
int P1 = 1, P2 = 1;
for (int i = 1; i < n; ++i) {
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
if (found(curHash1, curHash2))
++rez;
for (int i = n; i < bigString.size(); ++i) {
curHash1 = ((curHash1 - (bigString[i - n] * P1) % MOD1 + MOD1) * P + bigString[i]) % MOD1;
curHash2 = ((curHash2 - (bigString[i - n] * P2) % MOD2 + MOD2) * P + bigString[i]) % MOD2;
if (found(curHash1, curHash2))
++rez;
}
fout << rez;
return 0;
}