Cod sursa(job #1191635)

Utilizator heracleRadu Muntean heracle Data 28 mai 2014 11:15:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <cstring>

FILE* in;
FILE* out;

const int Q=10000000;
const int KEY=1<<20;

unsigned int lst[KEY],urm[Q],val[Q],nr;

bool exist(unsigned int x)
{
    int loc=lst[x%KEY];

    while(loc!=0)
    {
        if(val[loc]==x)
            return 1;
        loc=urm[loc];
    }
    return 0;
}

void add(unsigned int x)
{
    int loc=x%KEY;
    val[++nr]=x;
    urm[nr]=lst[loc];
    lst[loc]=nr;
}



char v[Q];
int size;

int main()
{
    in=fopen("abc2.in","r");
    out=fopen("abc2.out","w");

    fscanf(in,"%s\n",v);
    size=strlen(v);

    char act[20];
    int s;
    unsigned int val;
    unsigned int pow3;

    while(fscanf(in,"%s\n",act)>0)
    {
       // s=strlen(act);
        val=0;
        pow3=1;
        for(int j=0 ; act[j]!=0 ; j++)
        {
            val+=(act[j]-'a')*pow3;
            pow3*=3;
        }

        if(!exist(val))
            add(val);
    }

    long long rez=0;

    for(int i=0; i<size; i++)
    {
        val=0;
        pow3=1;
        for(int j=0; j<20; j++)
        {
            val+=(v[i+j]-'a')*pow3;
            if(exist(val))
                rez++;
        }
    }

    fprintf(out,"%lld",rez);

    return 0;
}