Cod sursa(job #2294550)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 2 decembrie 2018 15:55:18
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <fstream>

using namespace std;

const int p = 10003;
const int N = 100000001;

struct Nod
{
    Nod *next;
    int info;
} ;

int convert( char *s)
{
    unsigned long long hh = 0 , pp = 1;
    int i = strlen(s);
    for ( ; i >= 0; i-- )
    {
        hh = hh * pp + (s[i]- '0');
        pp *= 3;
    }
    return (int)(hh%p);
}

int h ( int x)
{
    return x % p;
}

void inserare ( Nod ** v, int x )
{
    Nod *prim ;
    int poz = h(x);

    for(prim = v[poz]; prim != NULL; prim = prim->next)
    {
        if ( prim ->info == x)
            return;
    }
    Nod *aux = new Nod;
    aux->next = NULL;
    aux->info = x;
    if( v[poz] == NULL )
        v[poz] = aux;
    else
    {
        aux->next = v[poz] ->next;
        v[poz]->next = aux;
    }
}

bool cautare( Nod** v, int x)
{
    Nod * prim ;
    if ( prim == NULL)
        return false;
    int poz = h(x);
    for(prim =  v[poz]; prim != NULL; prim = prim->next)
    {
        if ( prim ->info == x)
            return true;
    }
    return false;

}

void dealloc ( Nod ** v)
{
    int i;
    for (i = 0; i < p; i++)
    {
        delete(v[i]);
    }
    delete(v);
}

int main()
{
    ifstream in ("abc2.in");
    ofstream out("abc2.out");

    int nr, i, lcuv = 0, x, n;
    char ch,mak[N];
    Nod **v;
    char cuv[21] ;

    v = new Nod* [p+1];
    for ( i = 0 ; i < p; i++)
    {
        v[i] = new Nod [p+1];
        v[i] = NULL;
    }

    in >> mak >> cuv;

    if(cuv[strlen(cuv)-1] == '\n')
        cuv[strlen(cuv)-1] = '\0';
    lcuv = strlen(cuv);

    x = convert ( cuv );
    inserare( v, x);
    while (in >> cuv)
    {
        if(cuv[strlen(cuv)-1] == '\n')
            cuv[strlen(cuv)-1] = '\0';
        x = convert ( cuv );
        inserare( v , x );
    }

    in.close();

    nr = 0;
    n = strlen(mak);
    for ( i = lcuv; i < n; i++)
    {
        ch = mak[i];
        mak[i] = 0;
        x = convert(mak + i - lcuv );
        if( cautare(v,x))
                nr++;
        mak[i] = ch;
    }

    out << nr;

    out.close();

    dealloc ( v );

    return 0;
}