Cod sursa(job #1835582)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 27 decembrie 2016 02:33:14
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 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;
long long int pw[WSIZE];
char text[TSIZE];

vector <long long int> H[NMAX];

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

int main()
{
    int length, length_t;
    long long int val, app = 0;
    char word[WSIZE];
    ///
    pw[0] = 1;
    for (int i = 1; i < WSIZE; i++)
        pw[i] = pw[i - 1] * A;
    ///
    in >> text;
    ///
    in >> word;
    length = strlen(word);
    ///
    val = 0;
    for (int i = 0; i < length; i++)
        val += ((word[i] - 'a') * pw[i]);
    ///
    if (!_find(val))
        H[val % NMAX].push_back(val);
    while (in >> word)
    {
        val = 0;
        for (int i = 0; i < length; i++)
            val += ((word[i] - 'a') * pw[i]);
        if (!_find(val))
            H[val % NMAX].push_back(val);
    }
    in.close();
    ///
    val = 0;
    for (int i = 0; i < length; i++)
        val += ((text[i] - 'a') * pw[i]);
    ///
    length_t = strlen(text);
    for (int i = length; i < length_t; i++)
    {
        if (_find(val))
            app++;
        val = val / 3;
        val = val + (text[i] - 'a') * pw[length - 1];
    }
    if (_find(val))
        app++;
    out << app << "\n";
    out.close();
    return 0;
}