Cod sursa(job #1846222)

Utilizator ASD135Radu M ASD135 Data 12 ianuarie 2017 13:19:15
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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;
}