Cod sursa(job #944813)

Utilizator dariusdariusMarian Darius dariusdarius Data 29 aprilie 2013 19:36:29
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned int uint;
const uint hash_mod=666013;
vector<uint> H[hash_mod];
bool hash_find(const uint &hash_code)
{
    uint h=hash_code%hash_mod;
    for(auto &x : H[h])
        if(x==hash_code)
            return true;
    return false;
}
char s[10000005];
char w[25];
int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    uint hash_code=0,N,M,ans;
    gets(s);
    while(gets(w))
    {
        hash_code=0;
        for(int i=0;w[i];i++)
            hash_code=3u*hash_code+w[i]-'a';
        if(!hash_find(hash_code))
            H[hash_code%hash_mod].push_back(hash_code);
    }
    N=strlen(s);
    M=strlen(w);
    if(M>N)
    {
        printf("0\n");
        return 0;
    }
    uint p=1;hash_code=0;
    for(uint i=0;i<M;i++)
    {
        if(i) p=3u*p;
        hash_code=3*hash_code+s[i]-'a';
    }
    if(hash_find(hash_code))
        ans=1;
    else
        ans=0;
    for(uint i=M;i<N;i++)
    {
        hash_code-=p*(s[i-M]-'a');
        hash_code*=3u;
        hash_code+=(s[i]-'a');
        if(hash_find(hash_code))
            ans++;
    }
    printf("%u\n",ans);
    return 0;
}