Cod sursa(job #2433088)

Utilizator rd211Dinucu David rd211 Data 25 iunie 2019 19:39:58
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
struct item
{
    string word;
    int hashed;
};
vector<item> dictionary;
string sir;
short pows[21];
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;
}
int hashNext(string a,int hashA,char next)
{
    int r = 1;
    r = (dictionarySize*(hashA-a[0]*h)+next)%prime;
    while(r<0)
        r+=prime;
    return r;
}

void calcH(int m)
{
    for(int i = 0;i<m-1;i++)
        h=(h*dictionarySize)%prime;
}
void read()
{
    string temp;
    fin>>sir;
    for(int i = 0;i<sir.size();i++)
        sir[i]=sir[i]-'a'+1;
    while(fin>>temp)
    {
        for(int i = 0;i<temp.size();i++)
            temp[i]=temp[i]-'a'+1;
        dictionary.push_back({temp,hashf(temp)});
    }
    calcH(temp.size());
}
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++)
    {
        //for(int j = i;j<wordSize+i;j++)
         //   cout<<(int)sir[j];
        //cout<<" "<<f<<endl;
        for(int j = 0;j<dictionary.size();j++)
        {
            if(f==dictionary[j].hashed)
            {
               if(dictionary[j].word.compare(sir.substr(i,wordSize))==0){
                    times++;
                    break;
               }
            }
        }
        if(i<sir.size()-wordSize)
        {
            f=hashNext(sir.substr(i,wordSize),f,sir[i+wordSize]);
        }

    }
    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;
}