Cod sursa(job #2634426)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 10 iulie 2020 20:57:17
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <iostream>
#include <unordered_map>

using namespace std;

const int NMAX = 1e7 + 5;

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

int N;
char S[NMAX];

int L = 0;

unordered_map < int, bool > mp;

int ans = 0;

namespace InParser
{
static const int BSIZE = (1 << 16);

static int pos = BSIZE - 1;
static char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        int n = fread(buff, 1, BSIZE, stdin);

        if(n != BSIZE)
            for(int i = n; i < BSIZE; ++i)
                buff[i] = 0;
    }

    return buff[pos];
}
};

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()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

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

    for( ; ; )
    {
        char Ch = InParser :: Char();

        if(Ch >= 'a' && Ch <= 'z')
            S[++N] = Ch;
        else
            break;
    }

    int Key = 0;

    for( ; ; )
    {
        char Ch = InParser :: Char();

        if(Ch >= 'a' && Ch <= 'z')
        {
            ++L;

            Key = ((1LL * Key * Base) % (1LL * Mod) + (int)(Ch - 'a')) % (1LL * Mod);
        }
        else
            break;
    }

    mp[Key] = 1;

    bool Ok = 1;

    for( ; Ok; )
    {
        Key = 0;

        bool found = 0;

        for(int i = 1; i <= L && Ok; ++i)
        {
            char Ch = InParser :: Char();

            if(Ch >= 'a' && Ch <= 'z')
                Key = ((1LL * Key * Base) % (1LL * Mod) + (int)(Ch - 'a')) % (1LL * Mod), found = 1;
            else
            {
                Ok = 0;

                break;
            }
        }

        if(found)
            mp[Key] = 1, InParser :: Char();
    }

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

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

    return 0;
}