Pagini recente » Cod sursa (job #2483781) | Cod sursa (job #2696286) | Cod sursa (job #279506) | Cod sursa (job #234288) | Cod sursa (job #2572223)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int MAXD = 10000005, MAXN = 50005, BASE = 3, MOD = 15029;
int hsh[MAXN], n, s, p = 1;
char inp[MAXD];
void init(char *str)
{
s = strlen(str);
for (int i = 0; i < s - 1; ++i)
p = (p * BASE) % MOD;
}
int generateHash(char *str)
{
int h = 0;
for (int i = 0; i < s; ++i)
h = (h * BASE + (str[i] - 'a')) % MOD;
return h;
}
void read()
{
fin >> inp;
char str[MAXN];
fin >> str;
init(str);
hsh[n++] = generateHash(str);
while(fin >> str)
hsh[n++] = generateHash(str);
}
void solve()
{
int res = 0, h = generateHash(inp), nr = strlen(inp);
if (binary_search(hsh, hsh + n, h) == true)
++res;
for (int i = s; i < nr; ++i) {
h = (((h - ((inp[i - s] - 'a') * p) % MOD) + MOD) * BASE + (inp[i] - 'a')) % MOD;
if (binary_search(hsh, hsh + n, h) == true)
++res;
}
fout << res << '\n';
}
int main()
{
read();
sort(hsh, hsh + n);
solve();
return 0;
}