Cod sursa(job #1835770)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 27 decembrie 2016 13:47:41
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define TSIZE 10000001
#define WSIZE 21
#define NMAX 200003

using namespace std;

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

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

vector <unsigned int> H[NMAX];

unsigned int base3(const char* str)
{
    unsigned int length = strlen(str);
    unsigned int base3_val = 0;
    for (int i = length - 1, j = 0; i >= 0; i--, j++)
        base3_val += ((str[i] - 'a') * pw[j]);
    return base3_val;
}

int _find(unsigned int val)
{
    int key = val % NMAX;
    for (unsigned int i = 0; i < H[key].size(); i++)
        if (H[key][i] == val)
            return 1;
    return 0;
}

int main()
{
    int length, length_t, ok = 0;
    unsigned int val, 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))
    {
        val = base3(word);
        if (!ok)
            length = strlen(word), ok = 1;
        if (!_find(val))
            H[val % NMAX].push_back(val);
    }
    in.close();
    ///
    for (int i = 0; i < length; i++)
        word[i] = text[i];
    word[length] = '\0';
    ///
    val = base3(word);
    length_t = strlen(text);
    ///
    for (int i = length; i < length_t; i++)
    {
        if (_find(val))
            app++;
        val = val - ((text[i - length] - 'a') * pw[length - 1]);
        val = val * 3 + (text[i] - 'a');
    }
    if (_find(val))
        app++;
    out << app << "\n";
    out.close();
    return 0;
}