Cod sursa(job #1835368)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 26 decembrie 2016 19:17:14
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define TSIZE 10000001
#define WSIZE 21
#define NMAX 33343

using namespace std;

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

const int A = 3;
long long int pw[WSIZE];
char text[TSIZE];

struct mapp{
    char str[WSIZE];
};

vector <mapp> H[NMAX];

long long int rollh(const char* str)
{
    unsigned int length = strlen(str);
    long long int hcode = 0;
    for (unsigned int i = 0; i < length; i++)
        hcode += (str[i] * pw[i]);
    return hcode;
}

int hash_f(const char* str)
{
    return rollh(str) % NMAX;
}

int _find(const char* str, int key)
{
    for (unsigned int i = 0; i < H[key].size(); i++)
        if (strcmp(str, H[key][i].str) == 0)
            return i;
    return -1;
}

int main()
{
    mapp aux;
    int code, length, length_t, ok = 0;
    long long int app = 0;
    char word[WSIZE];
    ///
    pw[0] = 1;
    for (int i = 1; i < WSIZE; i++)
        pw[i] = pw[i - 1] * A;
    ///
    in.getline(text, TSIZE);
    while (in.getline(word, WSIZE))
    {
        code = hash_f(word);
        if (!ok)
            length = strlen(word), ok = 1;
        if (_find(word, code) == -1)
        {
            strcpy(aux.str, word);
            H[code].push_back(aux);
        }
    }
    in.close();
    ///
    for (int i = 0; i < length; i++)
        word[i] = text[i];
    word[length] = '\0';

    ///
    code = rollh(word);
    length_t = strlen(text);
    for (int i = length; i < length_t; i++)
    {
        if (_find(word, code % NMAX) != -1)
           app++;
        code = (code - text[i - length]) / A + text[i] * pw[length - 1];
        ///
        memmove(word, word + 1, length);
        word[length - 1] = text[i];
        word[length] = '\0';
    }
    if (_find(word, code % NMAX) != -1)
           app++;
    out << app << "\n";
    out.close();
    return 0;
}