Cod sursa(job #2433138)

Utilizator rd211Dinucu David rd211 Data 25 iunie 2019 22:42:11
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ofstream fout("abc2.out");
class InParser {
public:
	FILE *fin;
	char *buff;
	int sp;
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
};
InParser 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;
}

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

    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);
        while(j->hashed==f)
        {
            bool isEqual=true;
            for(int d = 0;d<wordSize;d++)
            {
                if(j->word[d]!=sir[i+d])
                    isEqual=false;
            }
            if(isEqual){
                times++;
                break;
            }
            j++;
        }

        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();
    solve();
    return 0;
}