Cod sursa(job #2440072)

Utilizator DavidLDavid Lauran DavidL Data 17 iulie 2019 15:17:02
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>
using namespace std;

#define cin fi
#define cout fo
ifstream fi("abc2.in");
ofstream fo("abc2.out");

const int baza = 3;
const int MOD1 = 1000003;
const int MOD2 = 1000033;

int n, m;
char A[10000005];
char a[25];
forward_list <int> M[MOD1];

inline int getMod(long long x, int M)
{
    return x - x / M * M;
}

void adauga(long long x)
{
    int nr1 = getMod(x, MOD1);
    int nr2 = getMod(x, MOD2);

    bool gasit = 0;
    for (auto x: M[nr1])
        if (x == nr2)
        {
            gasit = 1;
            break;
        }

    if (!gasit)
        M[nr1].push_front(nr2);
}

bool este(long long x)
{
    int nr1 = getMod(x, MOD1);
    int nr2 = getMod(x, MOD2);

    for (auto x: M[nr1])
        if (x == nr2)
            return 1;
    return 0;
}

int main()
{
    cin >> A + 1;
    n = strlen(A + 1);

    while (cin >> a + 1)
    {
        m = strlen(a + 1);
        long long cod = 0;
        for (int i = 1; i <= m; i++)
        {
            cod = cod * baza + (a[i] - 'a');
        }
        adauga(cod);
    }

    if (n < m)
    {
        cout << 0;
        return 0;
    }

    int rez = 0;

    long long p = 1;
    for (int i = 1; i < m; i++)
        p *= baza;

    long long cod = 0;
    for (int i = 1; i <= m; i++)
    {
        cod = cod * baza + (A[i] - 'a');
    }

    if (este(cod))
        rez++;

    for (int i = m + 1; i <= n; i++)
    {
        cod -= p * (A[i - m] - 'a');
        cod = cod * baza + (A[i] - 'a');

        if (este(cod))
            rez++;
    }

    cout << rez;

    return 0;
}