Cod sursa(job #2028192)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 27 septembrie 2017 12:31:57
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
# include <bits/stdc++.h>
# define ll long long
# define MOD 666013

using namespace std;

const int lgmax = 1e7 + 5,  cmax = 25;

char text[lgmax], s[cmax];

vector <ll> Hash[MOD + 5];

ll Search(ll x)
{
    int key = x % (1LL * MOD);
    for (auto &it: Hash[key])
        if (it == x) return 1;

    return 0;
}

int main ()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);

    int n, m, i;
    ll hash_a, hash_b;

    gets(text + 1), n = strlen(text + 1);

    gets(s + 1), m = strlen(s + 1);

    do
    {
        ll put = 1;
        hash_a = 0;

        for (i = m; i >= 1; --i)
            hash_a += 1LL * (put * (s[i] - 'a')), put *= 3LL;

        int key = hash_a % (1LL * MOD);

        Hash[key].push_back(hash_a);
        gets(s + 1);

    }
    while (!feof(stdin));

    ll put = 1;
    hash_b = 0;

    for (i = m; i >= 1; --i)
        hash_b += 1LL * (put * (text[i] - 'a')), put *= 3;

    ll ans = 0LL;
    put /= 3;
    int key = hash_b % MOD;

    if (find(Hash[key].begin(), Hash[key].end(), hash_b) != Hash[key].end()) ++ans;

    for (i = m + 1; i <= n; ++i)
    {
        hash_b -= 1LL * (put * (text[i - m] - 'a'));

        hash_b *= 3LL, hash_b += 1LL * (text[i] - 'a');

        int key = hash_b % MOD;
        if (find(Hash[key].begin(), Hash[key].end(), hash_b) != Hash[key].end()) ++ans;
    }

    printf("%lld\n", ans);

    return 0;
}