Cod sursa(job #2433163)

Utilizator rd211Dinucu David rd211 Data 26 iunie 2019 01:29:04
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ofstream fout("abc2.out");
const int prime = 1001;
const int dictionarySize = 3;
int wordSize;
string sir;
set<string> hmap[1001];
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 add(string a)
{
    int Hash = hashf(a);
    hmap[Hash].insert(a);
}

void calcH()
{
    for(int i = 0;i<wordSize-1;i++)
        h=(h*dictionarySize)%prime;
}
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;
	}
};
void read()
{
    InParser fin("abc2.in");
    string temp;
    char c;
    c = fin.read_ch();
    while(c!='\n')
        sir+=c-'a'+1,c=fin.read_ch();
    bool isDone = false;
    while(c=fin.read_ch())
    {
        if(c=='\n')
        {
            if(!isDone){
                wordSize = temp.size();
                isDone=true;
            }
            add(temp);
            temp="";
        }
        else
        {
            temp+=c-'a'+1;
        }
    }
    calcH();
}

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 solve()
{
    string temp = sir.substr(0,wordSize);
    int f = hashf(temp);
    int counter = 0;
    for(int i = 0;i<=sir.size()-wordSize;i++)
    {
        temp = sir.substr(i,wordSize);
        if(hmap[f].find(temp)!=hmap[f].end()){
            counter++;
        }
        if(i<sir.size()-wordSize)
        {
            f=hashNext(temp,f,sir[i+wordSize]);
        }
    }
    fout<<counter<<'\n';
}
int main()
{
    read();
    solve();
    return 0;
}