Cod sursa(job #2572223)

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