Cod sursa(job #2901436)

Utilizator stefanchpStefan Chiper stefanchp Data 13 mai 2022 18:38:20
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <cstring>
#include <stdlib.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
char s[10000005];
#define prim 9983
char cuv[22];
int main()
{
    fin >> s;
    fin >> cuv;
    unsigned int nr = 0, i, n = strlen(s), nc = strlen(cuv), putere = 1, j;
    for (i = 0; i < nc; i++)
    {
        nr += (cuv[i] - 'a') * putere;
        putere *= 3;
    }
    unsigned int loc = nr % prim;
    unsigned int** h = (unsigned int**)malloc(prim * sizeof(unsigned int*));
    unsigned int* ap = (unsigned int*)calloc(prim, sizeof(unsigned int));
    ap[loc]++;
    h[loc] = (unsigned int*)realloc(h[loc], ap[loc] * sizeof(unsigned int));
    h[loc][ap[loc] - 1] = nr;
    while (fin >> cuv)
    {
        nr = 0, putere = 1;
        for (i = 0; i < nc; i++)
        {
            nr += (cuv[i] - 'a') * putere;
            putere *= 3;
        }
        loc = nr % prim;
        ap[loc]++;
        h[loc] = (unsigned int*)realloc(h[loc], ap[loc] * sizeof(unsigned int));
        h[loc][ap[loc] - 1] = nr;
    }
    int sol = 0;
    nr = 0, putere = 1;
    for (i = 0; i < nc; i++)
    {
        nr += (s[i] - 'a') * putere;
        putere *= 3;
    }
    putere /= 3;
    loc = nr % prim;
    for (i = 0; i < ap[loc]; i++)
        if (h[loc][i] == nr) { sol++; break; }
    for (i = nc; i < n; i++)
    {
        nr -= s[i - nc] - 'a';
        nr /= 3;
        nr += (s[i] - 'a') * putere;
        loc = nr % prim;
        for (j = 0; j < ap[loc]; j++)
            if (h[loc][j] == nr) { sol++; break; }
    }
    fout << sol;
    return 0;
}