Cod sursa(job #1838739)

Utilizator BLz0rDospra Cristian BLz0r Data 1 ianuarie 2017 17:33:24
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define NMAX 10000002
#define LMAX 22
#define MOD 666013

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

vector <unsigned int> Hash[MOD + 1];
char s[NMAX], aux[LMAX];
unsigned int p3[LMAX];
int lg, LG;

inline int Number(char x) {

    return x - 'a';
}

inline unsigned int Key(unsigned int x) {

    return x % MOD;
}

void InsertValue(unsigned int x) {

    Hash[Key(x)].push_back(x);
}

bool FindValue(unsigned int x) {

    vector <unsigned int> :: iterator it;

    unsigned int k = Key(x);

    for (it = Hash[k].begin(); it != Hash[k].end(); ++it)
        if (*it == x)
            return 1;

    return 0;
}

// codificam in baza 3
unsigned int GetCode() {

    unsigned int ret = 0;

    for (int i = 0, j = lg; i <= lg; ++i, --j)
        ret = ret + Number(aux[i]) * p3[j];

    return ret;

}

int main() {

    fin >> s;
    LG = strlen(s) - 1;

    fin >> aux;
    lg = strlen(aux) - 1;

    p3[0] = 1;
    for (int i = 1; i <= 20; ++i)
        p3[i] = 3 * p3[i - 1];

    // hash-uim cuvintele din dictionar ca numere in baza 3
    do {

        unsigned int x = GetCode();
        if (!FindValue(x))
            InsertValue(x);

    }while (fin >> aux);

    // rezolvam prima bucata de lungime lg (cuvintele din dictionar)
    unsigned int T = 0;
    for (int i = 0, j = lg; i <= lg; ++i, --j)
        T = T + 1LL * Number(s[i]) * p3[j];

    int rez = FindValue(T);

    //facem rolling-hash pe sirul mare
    for (int i = lg + 1, j = 0; i <= LG; ++i, ++j) {

        T = T - 1LL * Number(s[j]) * p3[lg];
        T = T * 3 + Number (s[i]);

        rez += FindValue(T);
    }

    fout << rez;

    return 0;
}