Cod sursa(job #908708)

Utilizator FayedStratulat Alexandru Fayed Data 9 martie 2013 22:11:30
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <vector>
#include <cstring>
#define MOD 666013
using namespace std;

char S[10000003];
char cuvant[23];
vector < unsigned int > Hash[MOD];
unsigned int n,m;
ifstream f("abc2.in");
ofstream g("abc2.out");

void citesc(){

 f >> S;
    n = strlen(S);
 f >> cuvant;
    m = strlen(cuvant);
}

inline void Add(int X){

    unsigned int key = X%MOD;
    Hash[key].push_back(X);
}

inline short Search(unsigned int X){
    unsigned int key = X%MOD;
    for(vector <unsigned int >::iterator it = Hash[key].begin();it!=Hash[key].end();++it)
        if(*it == X)
            return 1;
return 0;
}

inline int Hashing(char *cuvant,unsigned int m){

     unsigned int P = 0;
     for(register unsigned int i=0;i<m;++i)
     P = (P*3 + cuvant[i] - 'a');

return P;
}

inline void solve(){

    unsigned int putere = 1;
    unsigned int T=0,P=0,nr=0;
    P = Hashing(cuvant,m);
    Hash[P%MOD].push_back(P);

    while(f >> cuvant){
        P = Hashing(cuvant,m);
        Hash[P%MOD].push_back(P);
    }

    for(register unsigned int i=1;i<m;++i)
        putere*=3;

    T = Hashing(S,m);
    nr+=Search(T);

    for(register unsigned int i=0;i<=n-m;++i){

        T = (T- (S[i]-'a') *putere)*3 + (S[i+m]-'a');
        nr+=Search(T);
}

   g << nr;
}

int main(){

    citesc();
    solve();

return 0;
}