Cod sursa(job #2295335)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 3 decembrie 2018 16:17:32
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<stdio.h>

#include<string.h>

#define M 393241

#define NMAX 10000005

FILE *fin,*fout;

struct node

{

    unsigned long long  info;

    node *urm;

};

node *hashtable[M];



unsigned long long hfunction(unsigned long long x)

{

    return x%M;

}



int searchnode(unsigned long long value)

{

    node *head = hashtable[hfunction(value)];



    while (head != NULL && head->info != value)

    {

        head = head->urm;

    }



    if (head != NULL)

    {

        return 1;

    }

    return 0;

}



void addnode(unsigned long long value)

{

    node *first = new node;

    first->info = value;

    first->urm = hashtable[hfunction(value)];

    hashtable[hfunction(value)] = first;

}



char sir[NMAX],cuvant[30];



unsigned long long lcuvant,lsir,i;



int main()

{
    fin=fopen("abc2.in","r");
    fout=fopen("abc2.out","w");
    fgets(sir,10000005,fin);
    lsir=strlen(sir);
    if(sir[lsir-1]=='\n'){sir[lsir-1]=0;lsir--;}

    fgets(cuvant,30,fin);
    lcuvant=strlen(cuvant);
    if(cuvant[lcuvant-1]=='\n'){cuvant[lcuvant-1]=0;lcuvant--;}

    unsigned long long value=0;



    for (i = 0; i <= lcuvant - 1; i++)

    {

        value = 3 * value + (cuvant[i] - 'a');

    }

    addnode(value);



    while (fgets(cuvant,30,fin)!=NULL)

    {

        unsigned long long value = 0;

        for (i = 0; i <= lcuvant - 1; i++)

        {

            value = 3 * value + (cuvant[i] - 'a');

        }



        if (searchnode(value) == 0)

        {

            addnode(value);

        }

    }



    unsigned long long p = 1;

    for (i = 1; i <= lcuvant - 1; i++)

    {

        p = p * 3;

    }

    unsigned long long rh = 0;



    for (i = 0; i <= lcuvant - 1; i++)

    {

        rh = 3 * rh + sir[i] - 'a';

    }



    int sol=0;



    sol = sol + searchnode(rh);



    lsir = strlen(sir);

    for (i = lcuvant; i <= lsir - 1; i++)

    {

        rh = rh - p * (sir[i - lcuvant] - 'a');

        rh = 3 * rh + (sir[i] - 'a');

        sol = sol + searchnode(rh);

    }



    fprintf(fout,"%d",sol);
    fclose(fin); fclose(fout);

    return 0;

}