Cod sursa(job #1191657)

Utilizator IonSebastianIon Sebastian IonSebastian Data 28 mai 2014 11:49:42
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int K = 1<<20, MAX_M = 10000000;

int lst[K], urm[MAX_M+1];
unsigned int val[MAX_M+1];

int nr, cuvL;

char v[MAX_M], cuv[20];

int 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 add(int x)
{
    if(!check(x))
    {
        int place = x&(K-1);
        val[++nr] = x;
        urm[nr] = lst[place];
        lst[place] = nr;
    }
}

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

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