Cod sursa(job #2588964)

Utilizator AlexBosneag26Bosneag Alexandru AlexBosneag26 Data 25 martie 2020 16:55:57
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <string>
#include <unordered_map>
#include <cmath>


using namespace std;

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

const int N = 10000001, M = 666019;

string text, str, str1;

long long val[N];

int lst[N], urm[N], nr;

int caracter3(char c)
{
    return c - 'a';
}

int hashf(string str)
{
    long long c = 0;
    for(int i = 0; i < str.length(); i++)
    {
        c = c * 3 + caracter3(str[i]);
    }
    return c;
}

int exista(long long x);

void adauga(string x)
{
    long long cod = hashf(x);
    int categ = cod % M;
    if(exista(cod))
    {
        return;
    }
    val[++nr] = cod;
    urm[nr] = lst[categ];
    lst[categ] = nr;
}

int exista(long long x)
{
    int categ = x % M;
    for(int p = lst[categ]; p != 0; p = urm[p])
    {
        if(val[p] == x)
            return 1;
    }
    return 0;
}

void sterge(int x)
{
    int categ = x % M;
    int p = lst[categ];
    if(val[p] == x)
    {
        lst[categ] = urm[p];
        return;
    }
    while(urm[p] != 0)
    {
        if(val[urm[p]] == x)
        {
            urm[p] = urm[urm[p]];
            return;
        }
        p = urm[p];
    }
}

int main()
{
    int lmax;
    getline(in, text);
    while(getline(in, str))
    {
        lmax = str.length();
        adauga(str);
    }
    str1 = text.substr(0, lmax);
    long long cod = hashf(str1), c = 0;
    if(exista(cod))
        c++;
    int st = lmax;
    long long p3 = pow(3, lmax - 1);
    for(int i = lmax; i < text.length(); i++)
    {
        cod = (cod - p3 * (text[i-lmax]-'a')) * 3 + (text[i]-'a');
        if(exista(cod))
        {
            c++;
        }
    }
    out << c;
    return 0;
}