Cod sursa(job #2572232)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 5 martie 2020 12:11:47
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#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;
}