Cod sursa(job #2961303)

Utilizator bem.andreiIceman bem.andrei Data 6 ianuarie 2023 09:08:39
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;
ifstream r("abc2.in");
ofstream w("abc2.out");

const int mod = 90907;
string s, cuv;
int lst[mod], urm[10000003], val[10000003], nr = 0, ls, lcuv;

bool ver(unsigned x)
{
    int c = x % mod, p = lst[c];
    while (p && val[p]!= x)
    {
        p = urm[p];
    }
    return p;
}

void adauga(unsigned x)
{
    if (ver(x))
    {
        return;
    }
    int c = x % mod;
    val[++nr] = x;
    urm[nr] = lst[c];
    lst[c] = nr;
}

unsigned hash_cuv()
{
    unsigned h = 0;
    for (int i = 0; i < lcuv; i++)
    {
        h = h * 3 + (cuv[i] - 'a');
    }
    return h;
}

int main()
{
    r >> s >> cuv;
    ls = s.size(), lcuv = cuv.size();
    if (ls < lcuv)
    {
        w << '0';
        return 0;
    }

    unsigned h;
    while(r >> cuv)
    {
        h = hash_cuv();
        adauga(h);
    }
    int rez = 0;
    h = 0;
    for (int i = 0; i < lcuv; i++)
    {
        h = h * 3 + (s[i] - 'a');
    }
    if (ver(h))
    {
        rez++;
    }
    unsigned p3 = pow(3, lcuv - 1);
    for (int i = lcuv; i < ls; i++)
    {
        h %= p3;
        h = h * 3 + (s[i] - 'a');
        if (ver(h))
        {
            rez++;
        }
    }
    w << rez;
    return 0;
}