Cod sursa(job #1191644)

Utilizator heracleRadu Muntean heracle Data 28 mai 2014 11:34:58
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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)
    {

        val=0;
        pow3=1;
        for(int j=0 ; act[j]!=0 ; j++)
        {
            val+=(act[j]-'a')*pow3;
            pow3*=3;
        }

        if(!exist(val))
            add(val);
    }
    s=strlen(act);

    val=0;
    pow3=1;
    int i=0;

    for( i=0; i<s; i++)
    {
        val+=(v[i]-'a')*pow3;

        if(i!=s-1)
            pow3*=3;
    }
    long long rez=0;

    if(exist(val))
        rez++;



    for( ; i<size; i++)
    {
        val/=3;
        val+=(v[i]-'a')*pow3;
        if(exist(val))
            rez++;
    }

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

    return 0;
}