Cod sursa(job #99780)

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

void convert(char S[], int p, unsigned &v)
{
    int i;

    v=S[p]-'a';
    for(i=p+1;i<p+w;++i)
        v=v*3+S[i]-'a';
}

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

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

    if(scanf("%s",W)!=1)
    {
        printf("0\n");
        return 0;
    }

    w=strlen(W); n=1;
    convert(W,0,A[0]);
    while(scanf("%s",W)==1)
        convert(W,0,A[n++]);

    sort(A,A+n);
    for(stp=1;stp<=n;stp<<=1); stp>>=1;
    for(i=0;i<=t-w;++i)
    {
        convert(T,i,v);
        for(p=-1,s=stp;s;s>>=1)
            if(p+s<n && A[p+s]<=v)
                p+=s;
        if(p>=0 && A[p]==v)
            ++ans;
    }

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