Cod sursa(job #1081100)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 13 ianuarie 2014 09:51:17
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

const char infile[] = "abc2.in";
const char outfile[] = "abc2.out";

ifstream fin(infile);
ofstream fout(outfile);

const int BASE = 3;
const int oo = 0x3f3f3f3f;
const int MOD = 1613;

typedef unsigned long long uint;
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

template <class T>
class Hash {
private:
    vector <T> _hash[MOD];
    inline int key(const int &value) {
        return value % MOD;
    }
public:
    inline void add(const T &value) {
        _hash[key(value)].push_back(value);
    }
    inline bool find(const T &value) {
        int keyy = key(value);
        for(typename vector < T> :: iterator it = _hash[keyy].begin(), fin = _hash[keyy].end(); it != fin ; ++ it)
            if(*it == value)
                return true;
        return false;
    }
};

inline uint getInt(const char &c) {
    return c - 'a';
}

string Text, s;
uint sigma;

inline int getValue(const string &p) {
    uint value = 0;
    uint i = 0;
    for(i = 0, sigma = p.size() ; i < sigma ; ++ i)
        value = value * BASE + getInt(p[i]);
    return value;
}

Hash <uint> _hash;

int main() {
    fin >> Text;
    while(fin >> s)
        _hash.add(getValue(s));
    uint value = 0;
    uint _base = 1;
    for(uint i = 0 ; i < sigma ; ++ i) {
        value = value * BASE + getInt(Text[i]);
        _base = _base * BASE;
    }
    uint Ans = 0;
    Ans += _hash.find(value);
    for(uint i = sigma , sz = Text.size() ; i < sz ; ++ i) {
        value = value * BASE + getInt(Text[i]);
        value = value - _base * getInt(Text[i - sigma]);
        Ans += _hash.find(value);
    }
    fout << Ans << '\n';
    fin.close();
    fout.close();
    return 0;
}