Cod sursa(job #2634435)

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

using namespace std;

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

typedef pair < int, int > PII;

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

const int Base_1 = 131, Mod_1 = 666013;
const int Base_2 = 137, Mod_2 = 666019;

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

int L, Key_1, Key_2;

map < PII, bool > mp;

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;
}

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 = ((1LL * Key_1 * Base_1) % (1LL * Mod_1) + (int)(A[i] - 'a')) % (1LL * Mod_1);

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

        mp[ {Key_1, Key_2}] = 1;
    }

    Key_1 = 0, Key_2 = 0;

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

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

    if(mp[ {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 = (1LL * p_1 * (int)(S[i - L] - 'a')) % (1LL * Mod_1);
        int Diff_2 = (1LL * p_2 * (int)(S[i - L] - 'a')) % (1LL * 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 = (1LL * Key_1 * Base_1) % (1LL * Mod_1), Key_2 = (1LL * Key_2 * Base_2) % (1LL * Mod_2);

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

        if(mp[ {Key_1, Key_2}])
            ++ans;
    }

    g << ans << '\n';

    return 0;
}