Cod sursa(job #1191645)

Utilizator IonSebastianIon Sebastian IonSebastian Data 28 mai 2014 11:35:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <cstring>

using namespace std;

FILE* in = fopen("abc2.in", "r");
FILE* out = fopen("abc2.out", "w");

const int MAX_N = 50000, K = 666013, MAX_M = 10000000;

int lst[K], urm[MAX_N+1];
long long val[MAX_N+1];

int nr, cuvL;

char v[MAX_M], cuv[20];

long long nrap;

bool inline check(int x)
{
    int p = lst[x&(K-1)];
    while(p != 0 && val[p] != x)
    {
        p = urm[p];
    }
    return p != 0;
}

void inline del(int x)
{
    int r = x&(K-1), p;
    if(x == val[lst[r]])
    {
        lst[r] = urm[lst[r]];
        return;
    }
    p = lst[r];
    while(urm[p] != 0 && val[urm[p]] != x)
    {
        p = urm[p];
    }
    if(val[urm[p]] == x)
    {
        urm[p] = urm[urm[p]];
    }
}

void inline add(int x)
{
    if(!check(x))
    {
        int place = x&(K-1);
        val[++nr] = x;
        urm[nr] = lst[place];
        lst[place] = nr;
    }
}

long long transf()
{
    int p = 1;
    long long x = 0;
    for(int i = 0; i < cuvL; i++)
    {
        x += p*(cuv[i]-'a');
        p *= 3;
    }
    return x;
}

/*void cmp(int start)
{
    for(int i = 0; i < cuvL; i++)
    {
        cuv[i] = v[start+i];
    }
    int x = transf();
    if(check(x))
    {
        nrap++;
    }
}*/

int main()
{
    int i;
    fscanf(in, "%s", v);
    fscanf(in, "%s", cuv);
    cuvL = strlen(cuv);
    int cuvV = strlen(v);
    long long r = transf();
    add(r);
    while(fscanf(in, "%s", cuv) != EOF)
    {
        r = transf();
        add(r);
    }
    long long x;
    for(i = 0; i < cuvL; i++)
    {
        cuv[i] = v[i];
        x = transf();
        if(check(x))
        {
            nrap++;
        }
    }
    long long pcuv = 1;
    for(i = 1; i < cuvL; i++)
    {
        pcuv *= 3;
    }
    for(i = cuvL; i < cuvV; i++)
    {
        x -= (v[i-1]-'a');
        x /= 3;
        x += (v[i]-'a')*pcuv;
        if(check(x))
        {
            nrap++;
        }
    }
    fprintf(out,"%d", nrap);
    return 0;
}