Pagini recente » Cod sursa (job #2823152) | Cod sursa (job #2669499) | Cod sursa (job #2395383) | Cod sursa (job #501448) | Cod sursa (job #2488577)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int MAXS = 1e7 + 10, MAXN = 5e4 + 10, MAXLEN = 25, MOD = 666013, BASE = 4;
char matrix[MAXN][MAXLEN], input[MAXS];
int hash1[MAXN], n, m, h, power = 1;
void read() {
fin.getline(input, MAXS);
while (fin.getline(matrix[n++], MAXLEN));
}
void preprocess() {
--n;
m = strlen(matrix[0]);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
hash1[i] = (hash1[i] * BASE + (matrix[i][j] - 'a' + 1)) % MOD;
}
for (int i = 0; i < m; ++i) {
h = (h * BASE + (input[i] - 'a' + 1)) % MOD;
if (i)
power = (power * BASE) % MOD;
}
}
int findPos() {
int pos = 0;
if (binary_search(hash1, hash1 + n, h))
++pos;
for (int i = m; input[i]; ++i) {
h = ((h - ((input[i - m] - 'a' + 1) * power) % MOD + MOD) * BASE + input[i] - 'a' + 1) % MOD;
if (binary_search(hash1, hash1 + n, h))
++pos;
}
return pos;
}
int main() {
read();
preprocess();
sort(hash1, hash1 + n);
fout << findPos();
return 0;
}