Cod sursa(job #1488164)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 17 septembrie 2015 23:52:12
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <math.h>

#define TXT_DIM 10000007
#define DIM 27
#define NMAX 50007

using namespace std;
char buff[TXT_DIM], tmp[DIM];
unsigned int v[NMAX], len, sze, pw, n, aux, ct, x;

int cautbin(unsigned value)
{
    unsigned step = 1<<16, first = 0, index;
    for(;step; step>>=1)
    {
        index = first + step;
        if(index <= n)
        {
            if(v[index] <= value)
            {
                first = index;
            }
        }
    }
    return first;
}
void solve()
{
    for(unsigned i = 1; i< len; ++i)
    {
        aux = aux*3 + (buff[i]-'a');
    }
    aux *=3;
    for(unsigned i = len; i<= sze; ++i)
    {
        aux += buff[i]-'a';
        x = cautbin(aux);
        //printf("aux = %d x = %d\n", aux, x);
        if(v[x] == aux) ct++;
        aux -= (buff[i-len+1]-'a')*pw;
        aux *=3;
    }
}

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    scanf("%s", buff+1);
    sze = strlen(buff+1);
    for(int i =1; scanf("%s", tmp) == 1; ++i)
    {
        //printf("%s\n", tmp);
        len = strlen(tmp);
        for(unsigned j = 1; j<= len; ++j)
        {
            v[i] = v[i]*3 + (tmp[j-1]-'a');
        }
        //printf("%d\n", v[i]);
        n = i;
    }
    pw = pow(3, len-1);
    sort(v+1, v+n+1);
    solve();
    printf("%d\n", ct);
    return 0;
}