Cod sursa(job #332056)

Utilizator freak93Adrian Budau freak93 Data 16 iulie 2009 14:47:42
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<cstring>
#include<cstdio>

using namespace std;

const int maxl=10000020;
const int prime=32452843;
const int hash_size=1<<21;

struct nod
{
    long long v;
    nod *next;
} *hash[hash_size];

inline nod *find(long long x)
{
    long long list=x;
    list*=prime;
    list>>=30;
    nod *i;
    for(i=hash[list];i;i=i->next)
        if(i->v==x)
            break;
    return i;
}

inline void insert(long long x)
{
    long long list=x;
    list*=prime;
    list>>=30;
    nod *i=find(x);
    if(i) return;
    i=new nod;
    i->v=x;
    i->next=hash[list];
    hash[list]=i;
}

char s[maxl],cuvant[50];

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    fgets(s,sizeof(s),stdin);

    long long x,scad;
    int i,n;
    while(!feof(stdin))
    {
        fgets(cuvant,sizeof(cuvant),stdin);
        x=0;
        for(i=0;cuvant[i]!='\n'&&cuvant[i]!=0;++i)
            x=x*3+cuvant[i]-'a';
        insert(x);
    }
    n=i;
    x=0;
    scad=1;
    for(i=1;i<n;++i)
        scad*=3;
    int p=0;
    for(i=0;i<n;++i)
        x=x*3+s[i]-'a';
    if(find(x))
        ++p;
    for(;s[i]!='\n'&&s[i]!=0;++i)
    {
        x-=(s[i-n]-'a')*scad;
        x*=3;
        x+=s[i]-'a';
        if(find(x))++p;
    }

    printf("%d\n",p);
    fclose(stdin);
    fclose(stdout);

    return 0;
}