Cod sursa(job #2296412)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 4 decembrie 2018 17:32:18
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
#define mod 11083
vector <unsigned int> v[mod];
unsigned int verificare_candidati(unsigned int nr)
{
    unsigned int i,aux,dimensiune;
    aux=nr%mod;//aplicam functia modulo
    dimensiune=v[aux].size();
    for(i=0;i<dimensiune;i++)
    {
        if(v[aux][i]==nr)//daca il gasim
        {
            return 1;//returnam 1
        }
    }
    return 0;//returnam 0
}
int main()
{
    ifstream fin("abc2.in");
    ofstream fout("abc2.out");
    string sir_initial,cuvant;
    unsigned int nr,p=1,nr_candidati=0,i;
    unsigned int lgcuv,lgsir;
    fin>>sir_initial; //citim sirul initial
    lgsir=sir_initial.size();
    fin>>cuvant;//citim primul cuvant
    lgcuv=cuvant.size();
    nr=0;
    for(i=0;i<lgcuv;i++)
    {
        nr*=3;
        nr+=(cuvant[i]-'a');
    }
    v[nr%mod].push_back(nr);//introducem codificarea primului cuvant in vector
    while(!fin.eof())//introducem urmatoarele cuvinte
    {
        fin>>cuvant;
        nr=0;
        for(i=0;i<lgcuv;i++)
        {
             nr*=3;
             nr+=(cuvant[i]-'a');//scadem din caracter 'a', caracterul minim din sistemul limbii makako
        }
        v[nr%mod].push_back(nr);//adaugam in vector
    }
    nr=0;
    for(i=0;i<lgcuv;i++)
    {
        p*=3;
        nr*=3;
        nr+=(sir_initial[i]-'a');
    }
    p/=3;//inmultim p cu 3 de lgcuv-1 ori
    if(verificare_candidati(nr)==1)
    {
          nr_candidati++;
    }
    for(i=lgcuv;i<lgsir;i++) //lgcuv pastreaza lungimea unui cuvant normal
    {                         //lgsir pastreaza lungimea sirului initial
        nr-=p*(sir_initial[i-lgcuv]-'a');
        nr*=3;//inmultim cu 3, deoarece avem 3 litere in limba Makako a,b,c
        nr+=(sir_initial[i]-'a');//
        if(verificare_candidati(nr)==1)//verificam daca codificarea unui cuvant este candidat
        {
            nr_candidati++;//contorizam
        }
    }
    fout<<nr_candidati;
    fin.close();
    fout.close();
    return 0;
}