Cod sursa(job #1846036)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 12 ianuarie 2017 03:20:46
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb

#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

ifstream ka("abc2.in");
ofstream ki("abc2.out");
const int N_MAX = 50000;
string text, s;
int rezultat, sol, lista[N_MAX + 1], step;

bool cautare(int cautat)
{
    int i = 0;
    for(int k = step; k >= 0; k--)
        if(i + (1 << k) <= lista[0] && lista[i + (1 << k)] <= cautat)
            i += (1 << k);
    return lista[i] == cautat;
}

int main()
{
    getline(ka, text);
    int marime;
    while(getline(ka, s))
    {
        marime = s.size();
        int nr = 0;
        for(int i = 0; i < marime; i++)
            nr = nr * 3 + s[i] - 'a';
        lista[++lista[0]] = nr;
    }
    sort(lista + 1, lista + lista[0] + 1);
    int cautat = 0;
    int putere = 0;
    for(int i = 0; i < marime; i++)
    {
        cautat = 3 * cautat + text[i] - 'a';
        putere++;
    }
    for(; (1 << step) <= lista[0]; step++);
    putere--;
    int produs = pow(3, putere);
    if(cautare(cautat))
        sol++;
    for(int i = marime; i < text.size(); i++)
    {
        cautat -= (text[i - marime] - 'a') * produs;
        cautat = cautat * 3 + text[i] - 'a';
        if(cautare(cautat))
            sol++;
    }
    ki << sol;
}