Cod sursa(job #2433123)

Utilizator rd211Dinucu David rd211 Data 25 iunie 2019 21:19:46
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ofstream fout("abc2.out");
ifstream fin("abc2.in");
struct item
{
    string word;
    int hashed;
};
item dictionary[50010];
int dicSize = 0;
string sir;
const int prime = 101;
const int dictionarySize = 3;
int h = 1;
int hashf(string a)
{
    int r=0;
    for(int i = 0; i<a.size(); i++)
        r = (dictionarySize*r+a[i])%prime;
    return r;
}

void calcH(int m)
{
    for(int i = 0; i<m-1; i++)
        h=(h*dictionarySize)%prime;
}
bool compare(const item& f,const item& s)
{
    return f.word<s.word;
}
bool compare2(const item& f,const int& s)
{
    return f.hashed<s;
}
void read()
{
    string temp="";
    char c;
    fin.get(c);
    while(c!='\n')
        sir+=c-'a'+1,fin.get(c);
    while(fin.get(c))
    {
        if(c=='\n')
        {
            dictionary[dicSize++]={temp,hashf(temp)};
            temp="";
        }
        else
        {
            temp+=(c-'a'+1);
        }
    }
    calcH(dictionary[0].word.size());
    sort(dictionary,dictionary+dicSize,compare);
}
void solve()
{
    int times = 0;
    int wordSize = dictionary[0].word.size();
    int f = hashf(sir.substr(0,wordSize));
    for(int i = 0; i<=sir.size()-wordSize; i++)
    {
        item* j = lower_bound(dictionary,dictionary+dicSize,f,compare2);
        if(j->hashed==f)
        {
            if(j->word.compare(sir.substr(i,wordSize))==0)
            {
                times++;
            }
        }

        if(i<sir.size()-wordSize)
        {
            f = (dictionarySize*(f-sir[i]*h)+sir[i+wordSize])%prime;
            while(f<0)
                f+=prime;
        }

    }
    fout<<times<<'\n';
}
int main()
{
    read();
    //for(int i = 0;i<dictionary.size();i++)
    //{
    //    for(int j = 0;j<dictionary[i].word.size();j++)
    //        cout<<(int)dictionary[i].word[j];
    //    cout<<" "<<dictionary[i].hashed<<endl;
    //}
    solve();
    return 0;
}