Cod sursa(job #1488145)

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

#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[DIM], n, aux, ct, x;

void init()
{
    pw[0] = 1;
    for(int i = 1; i< 20; ++i) pw[i] = pw[i-1] * 3;
}

int cautbin(int value)
{
    int step = 1<<20, first = 0, index;
    for(;step; step>>=1)
    {
        index = first + step;
        if(index <= n)
        {
            if(v[index] <= value)
            {
                first = index;
            }
        }
    }
    return first;
}
void solve()
{
    for(int i = 1; i< len; ++i)
    {
        aux += (buff[i]-'a')*pw[len-i];
    }
    for(int 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[len-1];
        aux *=3;
    }
}

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    init();
    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(int j = 1; j<= len; ++j)
        {
            v[i] += (tmp[len-j]-'a')*pw[j-1];
        }
        //printf("%d\n", v[i]);
        n = i;
    }
    sort(v+1, v+n+1);
    solve();
    printf("%d\n", ct);
    return 0;
}