Cod sursa(job #2295904)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 4 decembrie 2018 00:23:17
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<fstream>
#include<cstring>
#include<math.h>
#define M 37215
#define N 10000045

using namespace std;

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

struct node
{
    unsigned int  info;
    node *urm;
};
node *hashtable[M];
char sir[N],cuv[25];

bool verify(unsigned int x)
{
    node *first = hashtable[x%M];

    while (first != NULL && first->info != x)
    {
        first = first->urm;
    }

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

void push(unsigned int x)
{
    node *first = new node;
    first->info = x;
    first->urm = hashtable[x%M];
    hashtable[x%M] = first;
}
unsigned int i;
int main()
{
    fin >> sir;
    fin >> cuv;

    unsigned int lcuv = strlen(cuv);
    unsigned int lsir = strlen(sir);

    unsigned int x=0;

    for (i = 0; i <= lcuv - 1; i++)
    {
        x = 3 * x + (cuv[i] - 'a');
    }
    push(x);

    while (fin >> cuv)
    {
        x = 0;
        for (i = 0; i <= lcuv - 1; i++)
        {
            x = 3 * x + (cuv[i] - 'a');
        }

        if (verify(x) == 0)
        {
            push(x);
        }
    }

    unsigned int p =pow(3,lcuv-1);
    unsigned int rollinghash = 0;

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

    long long ans=0;

    ans = ans + verify(rollinghash);

    for (i = lcuv; i <= lsir - 1; i++)
    {
        rollinghash = rollinghash - p * (sir[i - lcuv] - 'a');
        rollinghash = 3 * rollinghash + (sir[i] - 'a');
        ans = ans + verify(rollinghash);
    }

    fout << ans;

    fin.close();
    fout.close();
    return 0;
}