Cod sursa(job #1488173)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 18 septembrie 2015 00:10:42
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <vector>

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

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

struct hashulet
{
    vector<unsigned> v;
} tabel[MOD];

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';
        ///verificare
        int ceva = aux%MOD, sze1 = tabel[ceva].v.size();
        for(int j = 0; j< sze1; ++j)
            if(tabel[ceva].v[j] == aux)
            {
                ct++;
                break;
            }
        aux -= (buff[i-len+1]-'a')*pw;
        aux *=3;
    }
}

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