Pagini recente » Cod sursa (job #1805813) | Cod sursa (job #1685830) | Cod sursa (job #1531997) | Cod sursa (job #1014246) | Cod sursa (job #3267589)
#include <bits/stdc++.h>
using namespace std;
const int p = 3, MOD = (1 << 17) - 1;
vector<unsigned int> m[MOD];
bool searchHash(unsigned int k) {
unsigned int r = k & MOD;
for (int i = 0; i < (int)m[r].size(); ++i) {
if (m[r][i] == k) {
return 1;
}
}
return 0;
}
void insertHash(unsigned int k) {
unsigned int r = k & MOD;
if (!searchHash(k)) {
m[r].push_back(k);
}
}
unsigned int hashF(string word) {
unsigned int res = 0;
for (int i = 0; i < (int)word.size(); ++i) {
res = res * p + (word[i] - 'a');
}
return res;
}
unsigned int calcPow(int base, int power) {
unsigned int res = 1;
for (int i = 1; i <= power; ++i) {
res *= base;
}
return res;
}
int main() {
ifstream cin("abc2.in");
ofstream cout("abc2.out");
int wSize;
int buffSize = 1e5;
char buffer[buffSize + 1];
bool firstLineEnded = 0;
string text = "";
while(cin) {
cin.read(buffer, buffSize);
int buffLength = cin.gcount();
for(int i = 0; i < buffLength; ++i) {
if(!firstLineEnded) {
if(buffer[i] == '\n') {
firstLineEnded = 1;
}
} else {
if(buffer[i] == '\n') {
insertHash(hashF(text));
wSize = text.size();
text = "";
}
else {
text += buffer[i];
}
}
}
}
cin.close();
ifstream ffin("abc2.in");
unsigned int res = 0, ans = 0;
unsigned int last = calcPow(3, wSize - 1);
text = "";
bool ok = 0;
deque<int> D;
while(ffin) {
ffin.read(buffer, buffSize);
int buffLength = ffin.gcount();
for (int i = 0; i < buffLength; ++i) {
if(buffer[i] == '\n') {
cout << ans;
return 0;
}
int c = buffer[i] - 'a';
res = res * p + c;
D.push_back(c);
if(i >= wSize - 1) ok = 1;
if (ok) {
if (searchHash(res)) {
++ans;
}
res = res - last * D[0];
D.pop_front();
}
}
}
}