Cod sursa(job #2634431)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 10 iulie 2020 21:04:27
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <cstring>
#include <unordered_map>

using namespace std;

ifstream f ("abc2.in");
ofstream g ("abc2.out");

const int NMAX = 1e7 + 5, LMAX = 25;

const int Base = 131, Mod = 1e9 + 7;

int N;
char S[NMAX], A[LMAX];

int L, Key;

unordered_map < int, bool > mp;

int ans = 0;

static inline int lgput (int n, int p)
{
    int ans = 1, aux = n;

    for(int i = 0; (1 << i) <= p; ++i)
    {
        if(p & (1 << i))
            ans = (1LL * ans * aux) % (1LL * Mod);

        aux = (1LL * aux * aux) % (1LL * Mod);
    }

    return ans;
}

int main()
{
    f.tie(nullptr);

    f >> (S + 1);
    N = (int)strlen(S + 1);

    while(f >> (A + 1))
    {
        L = (int)strlen(A + 1), Key = 0;

        for(int i = 1; i <= L; ++i)
            Key = ((1LL * Key * Base) % (1LL * Mod) + (int)(A[i] - 'a')) % (1LL * Mod);

        mp[Key] = 1;
    }

    Key = 0;

    for(int i = 1; i <= L; ++i)
        Key = ((1LL * Key * Base) % (1LL * Mod) + (int)(S[i] - 'a')) % (1LL * Mod);

    if(mp[Key])
        ++ans;

    int p = lgput(Base, (L - 1));

    for(int i = (L + 1); i <= N; ++i)
    {
        int Diff = (1LL * p * (int)(S[i - L] - 'a')) % (1LL * Mod);

        Key -= Diff;
        if(Key < 0)
            Key += Mod;

        Key = (1LL * Key * Base) % (1LL * Mod);
        Key = (Key + (int)(S[i] - 'a')) % Mod;

        if(mp[Key])
            ++ans;
    }

    g << ans << '\n';

    return 0;
}