Cod sursa(job #1191632)

Utilizator IonSebastianIon Sebastian IonSebastian Data 28 mai 2014 11:13:21
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 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];
unsigned int val[MAX_N+1];

int nr, cuvL;

char v[MAX_M], cuv[20];

unsigned 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 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;
    }
}

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;
}

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);
    unsigned int r = transf();
    add(r);
    while(fscanf(in, "%s", &cuv[0]) != EOF)
    {
        r = transf();
        add(r);
    }
    for(i = 0; i < strlen(v)-cuvL; i++)
    {
        cmp(i);
    }
    fprintf(out,"%d", nrap);
    return 0;
}