Cod sursa(job #492724)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 15 octombrie 2010 17:34:27
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <algorithm>
#include <string>

using namespace std;

#define maxn 10000010
#define maxs 50010
#define baza 3

int n, i, j, nr, k, ps, pt, sol, h, lg;
int f[maxs];
int hs[maxs], pmax;
char s[maxn];
char c[25];

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    gets(s+1);
    while(gets(c+1))
    {
        ++nr;
        lg=1;
        while(c[lg]>0)
        {
            hs[nr]=(hs[nr]*baza+c[lg]-'a');
            ++lg;
        }
    }
    sort(hs+1, hs+nr+1);
    lg--;
    pmax=1;
    for(int i=1; i<lg; ++i)
        pmax=pmax*baza;
    ps=1;
    while(ps*2<=nr)
        ps*=2;
    for(int i=1; s[i]!=0; ++i)
    {
        if(i>lg)
            h-=(s[i-lg]-'a')*pmax;
        h=h*baza+s[i]-'a';
        if(i<lg) continue;
        pt=ps;
        for(j=1; pt; pt>>=1)
        {
            if(j+pt>nr)
                continue;
            if(hs[j+pt]<=h)
                j+=pt;
        }
        if(hs[j+pt]==h)
            sol++;
    }
    printf("%d\n", sol);
    return 0;
}