Cod sursa(job #1416609)

Utilizator toranagahVlad Badelita toranagah Data 8 aprilie 2015 15:27:24
Problema Aho-Corasick Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
//Problem d from baraj15
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
typedef int var;

#define MAXC 10005
#define MAXL 100005

ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

string text;

string cuv;
unordered_map<var, bool> Check;
unordered_map<var, var> hMap;
vector<var> Sol;
var n;

const var SIZE = 5;
const var B[SIZE] = {8172132, 1239831, 39821, 12379, 223918};
const var BASE = 12837;

var H[SIZE];

void addHash(char val);
void emptyHash();

void Read() {
    fin>>text;

    fin>>n;
    Sol.resize(n);

    for(var i=0; i<n; i++) {
        fin>>cuv;

        emptyHash();
        for(auto c : cuv)
            addHash(c);

        var h = 0;
        for(var i=0; i<SIZE; i++)
            h = h * BASE + H[i];

        cerr << "Hash of " << cuv << ": " << h << '\n';

        Check[cuv.size()] = 1;
        hMap[h] = i;
    }
}

void addHash(char val) {
    for(var i=0; i<SIZE; i++) {
        H[i] = H[i] * B[i] + val;
    }
}

void checkHash() {

    var h = 0;

    for(var i=0; i<SIZE; i++) {
        h = h * BASE + H[i];
    }

    cerr << "Checking " << h << "\n";

    if(hMap.find(h) == hMap.end())
        return;
    cerr << "Found: " << hMap[h] << '\n';
    Sol[hMap[h]] ++;
}


var PUT[SIZE][MAXL], COMP[SIZE][MAXL];
var put(var basei, var e) {
    if(COMP[basei][e])
        return PUT[basei][e];

    if(e == 0) return 1;

    PUT[basei][e] = B[basei] * put(basei, e-1);
    COMP[basei][e] = 1;

    return PUT[basei][e];
}

void subHash(char val, var len) {
    for(var i=0; i<SIZE; i++) {
        H[i] -= put(i, len) * val;
    }
}

void emptyHash() {
    for(var i=0; i<SIZE; i++) {
        H[i] = 0;
    }
}

void Solve(var length) {
    emptyHash();
    for(var i=0; i<length; i++)
        addHash(text[i]);
    checkHash();

    for(var i=length; i<text.size(); i++) {
        addHash(text[i]);
        subHash(text[i-length], length);
        checkHash();
    }
}

int main() {
    Read();

    for(auto &l : Check) {
        Solve(l.first);
    }

    for(var i=0; i<n; i++) {
        fout<<Sol[i]<<'\n';
    }



	return 0;
}