Pagini recente » Cod sursa (job #2099888) | Cod sursa (job #2047997) | Cod sursa (job #1253944) | Cod sursa (job #2498632) | Cod sursa (job #2572232)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int MAXD = 10000005, MAXN = 50005, MOD = 15029, MAXS = 20;
typedef unsigned int uint;
uint power[MAXS + 5], s, n;
vector<uint> hsh[MOD + 5];
char str[MAXN], inp[MAXD];
void preprocess()
{
power[0] = 1;
for (int i = 1; i < MAXS; ++i)
power[i] = power[i - 1] * 3;
}
bool findStr(int val)
{
int ind = val % MOD;
for (const auto& it: hsh[ind])
if (it == val)
return true;
return false;
}
uint toBase3(char *str)
{
uint res = 0;
for (int i = 0; i < s; ++i)
res += power[i] * (str[i] - 'a');
return res;
}
int main()
{
uint val, res = 0;
fin >> inp;
n = strlen(inp);
preprocess();
while (fin >> str) {
s = strlen(str);
val = toBase3(str);
if (findStr(val) == false)
hsh[val % MOD].push_back(val);
}
val = toBase3(inp);
if (findStr(val) == true)
++res;
for (int i = s; i < n; ++i) {
val -= (inp[i - s] - 'a');
val /= 3;
val += power[s - 1] * (inp[i] - 'a');
if (findStr(val) == true)
++res;
}
fout << res << '\n';
return 0;
}