Cod sursa(job #99812)

Utilizator sealTudose Vlad seal Data 11 noiembrie 2007 16:41:50
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.06 kb
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Tm 10000001
#define Nm 50000
#define Wm 21
char T[Tm];

int main()
{
    char W[Wm];
    int n,t,w,i,stp,s,j,ans=0;
    unsigned A[Nm],p3,v;

    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    gets(T); t=strlen(T);

    n=w=0;
    while(scanf("%s",W)==1)
    {
        A[n]=W[0]-'a';
        for(i=1;W[i];++i)
            A[n]=A[n]*3+W[i]-'a';
        ++n;
        if(!w)
            w=strlen(W);
    }

    if(!n || w>t)
    {
        printf("0\n");
        return 0;
    }

    sort(A,A+n);
    for(stp=1;stp<=n;stp<<=1); stp>>=1;
    for(p3=1,i=1;i<w;++i,p3*=3);
    
    for(v=i=0;i<=t;++i)
    {
        if(i>=w)
            v-=(T[i-w]-'a')*p3;
        v=v*3+T[i]-'a';
        if(i>=w-1)
        {
            for(j=-1,s=stp;s;s>>=1)
                if(j+s<n && A[j+s]<=v)
                    j+=s;
            if(j>=0 && A[j+s]==v)
                ++ans;
        }
    }

    printf("%d\n",ans);
    return 0;
}