Cod sursa(job #908521)

Utilizator FayedStratulat Alexandru Fayed Data 9 martie 2013 16:27:14
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 21
#define MOD 10007
using namespace std;

char S[10000001];
char cuvant[21];
vector < int > Hash[MOD];

int n,m,P,T,nr;

void citesc(){

    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    fgets(S,sizeof(S),stdin);
    n = strlen(S);
   scanf("%s",&cuvant);
    m = strlen(cuvant);
}

inline void Add(int X){

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

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

inline int Hashing(char *cuvant, int m){
     int P = 0;
     for(register int i=0;i<m;++i)
     P = (P*3 + cuvant[i] - 'a');

return P;
}

inline void solve(){

    citesc();

    int putere = 1;
    P = Hashing(cuvant,m);
    Hash[P%MOD].push_back(P);
    while(gets(cuvant)){
        P = Hashing(cuvant,m);
        Hash[P%MOD].push_back(P);
    }

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

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

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

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

    printf("%d",nr);
}

int main(){

    solve();

return 0;
}