Cod sursa(job #2634449)

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

using namespace std;

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

typedef pair < int, int > PII;

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

const int Base = 131, Mod = 666013;

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

unsigned int Key = 0;

int Where[MMAX], Last[(Mod + 5)], pos[MMAX];
unsigned int Val[MMAX];

int ans = 0;

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

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

        aux *= aux;
    }

    return ans;
}

static inline bool Ok (unsigned int k)
{
    for(int i = Last[k % Mod]; i; i = pos[i])
        if(Val[i] == k)
            return 1;

    return 0;
}

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 = Key * Base + (int)(A[i] - 'a');

        if(Ok(Key))
            continue;

        Where[++M] = Key % Mod;
        Val[M] = Key;

        if(Last[Key % Mod])
            pos[M] = Last[Key % Mod];

        Last[Key % Mod] = M;
    }

    Key = 0;

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

    if(Ok(Key))
        ++ans;

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

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

        Key = (Key - Diff) * Base + (int)(S[i] - 'a');

        if(Ok(Key))
            ++ans;
    }

    g << ans << '\n';

    return 0;
}