Cod sursa(job #2295322)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 3 decembrie 2018 16:05:38
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include<fstream>

#include<cstring>

#define M 10000511

#define NMAX 10000005

 

using namespace std;

 

ifstream fin("abc2.in");

ofstream fout("abc2.out");

 

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

    fin >> cuvant;

 

    lcuvant = strlen(cuvant);

 

    unsigned long long value=0;

 

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

    {

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

    }

    addnode(value);

 

    while (fin >> cuvant)

    {

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

    }

 

    unsigned long long 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);

    }

 

    fout << sol;

 

    fin.close();

    fout.close();

    return 0;

}