Cod sursa(job #2295037)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 3 decembrie 2018 00:15:14
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#include<cstring>
#define M 393241
#define NMAX 10000075

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

struct node
{
    long long  info;
    node *urm;
};
node *hashtable[M];

long long hfunction(long long x)
{
    return x%M;
}

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

    while (head != NULL && head->info != value)
    {
        head = head->urm;
    }

    if (head != NULL)
    {
        return 1;
    }
    return 0;
}

void addnode(int value)
{
    node *first = new node;
    first->info = value;
    first->urm = hashtable[hfunction(value)];
    hashtable[hfunction(value)] = first;
}


long long lcuvant,lsir,i;

int main()
{
    char sir[NMAX],cuvant[30];
    fin >> sir;
    fin >> cuvant;

    lcuvant = strlen(cuvant);

    long long value=0;

    for (i = 0; i <= lcuvant - 1; i++)
    {
        value = 3 * value + (cuvant[i] - 'a');
    }
    addnode(value);

    while (fin >> cuvant)
    {
        long long value = 0;
        for (i = 0; i <= lcuvant - 1; i++)
        {
            value = 3 * value + (cuvant[i] - 'a');
        }

        if (searchnode(value) == 0)
        {
            addnode(value);
        }
    }

    long long p = 1;
    for (i = 1; i <= lcuvant - 1; i++)
    {
        p = p * 3;
    }
    long long rh = 0;

    for (i = 0; i <= lcuvant - 1; i++)
    {
        rh = 3 * rh + sir[i] - 'a';
    }

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