Cod sursa(job #1083169)

Utilizator Theorytheo .c Theory Data 15 ianuarie 2014 18:10:13
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <cstring>
#include <vector>


#define getNumber(x) (x - 'a')
#define unsigned long long

using namespace std;

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

const unsigned NMAX = 10000009;
const unsigned M = 40009;

int N; char S[NMAX]; char P[30];

class Hash {

    public:

    vector<unsigned> H[M + 1];

    void insert(unsigned value) {

        H[value % M].push_back(value);
    }

    bool search(unsigned value) {

        int ind = value % M;

        for(unsigned i = 0 ;i < H[ind].size(); ++i)
            if(value == H[ind][i])
                return true;
        return false;
    }
};

Hash T;

void Read() {

    fin >> S + 1;
    while(!fin.eof()) {

        fin >> P; unsigned h = 0;

        N = strlen(P);

        for(int i = 0 ; i < strlen(P) ; ++i)
           h = h * 3 + getNumber(P[i]);

        T.insert(h);
    }

}

int main() {

   Read ();

   unsigned h = 0; unsigned cnt = 0; unsigned pw[22];

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

   for(int i = 1; i <= N; ++i) h = h * 3 + getNumber(S[i]);

   if(T.search(h)) cnt++;

   for(int i = N + 1; i < strlen(S + 1) ; ++i) {

        h -= getNumber(S[i - N]) * pw[N - 1];
        h = h * 3 + getNumber(S[i]);

        if(T.search(h)) cnt++;
   }

    fout << cnt <<'\n';

   return 0;
}