Cod sursa(job #2634447)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 10 iulie 2020 21:44:01
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 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_1 = 131, Mod_1 = 666013;
const int Base_2 = 137, Mod_2 = 666019;

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

int L, Key_1, Key_2;

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

int ans = 0;

static inline int lgput (int n, int p, int Mod)
{
    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;
}

static inline bool Ok (int k_1, int k_2)
{
    for(int i = Last[k_1]; i; i = pos[i])
        if(Val[i] == k_2)
            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_1 = 0, Key_2 = 0;

        for(int i = 1; i <= L; ++i)
        {
            Key_1 = ((Key_1 * Base_1) % Mod_1 + (int)(A[i] - 'a')) % Mod_1;

            Key_2 = ((Key_2 * Base_2) % Mod_2 + (int)(A[i] - 'a')) % Mod_2;
        }

        if(Ok(Key_1, Key_2))
            continue;

        Where[++M] = Key_1;
        Val[M] = Key_2;

        if(Last[Key_1])
            pos[M] = Last[Key_1];

        Last[Key_1] = M;
    }

    Key_1 = 0, Key_2 = 0;

    for(int i = 1; i <= L; ++i)
    {
        Key_1 = ((Key_1 * Base_1) % Mod_1 + (int)(S[i] - 'a')) % Mod_1;

        Key_2 = ((Key_2 * Base_2) % Mod_2 + (int)(S[i] - 'a')) % Mod_2;
    }

    if(Ok(Key_1, Key_2))
        ++ans;

    int p_1 = lgput(Base_1, (L - 1), Mod_1), p_2 = lgput(Base_2, (L - 1), Mod_2);

    for(int i = (L + 1); i <= N; ++i)
    {
        int Diff_1 = (p_1 * (int)(S[i - L] - 'a')) % Mod_1;
        int Diff_2 = (p_2 * (int)(S[i - L] - 'a')) % Mod_2;

        Key_1 -= Diff_1, Key_2 -= Diff_2;

        if(Key_1 < 0)
            Key_1 += Mod_1;

        if(Key_2 < 0)
            Key_2 += Mod_2;

        Key_1 = (Key_1 * Base_1) % Mod_1, Key_2 = (Key_2 * Base_2) % Mod_2;
        Key_1 = (Key_1 + (int)(S[i] - 'a')) % Mod_1, Key_2 = (Key_2 + (int)(S[i] - 'a')) % Mod_2;

        if(Ok(Key_1, Key_2))
            ++ans;
    }

    g << ans << '\n';

    return 0;
}