Cod sursa(job #1846043)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 12 ianuarie 2017 03:50:23
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb

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

ifstream ka("abc2.in");
ofstream ki("abc2.out");
const int MOD = 20011;
string text, s;
int sol;
vector <unsigned> lista[MOD];

bool cautare(int de_cautat, unsigned cautat)
{
    for(vector<unsigned>::iterator it = lista[de_cautat].begin(); it != lista[de_cautat].end(); ++it)
        if(*it == cautat)
            return true;
    return false;
}

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