Cod sursa(job #1782896)

Utilizator zacuscaAlex Iordache zacusca Data 18 octombrie 2016 16:59:15
Problema Abc2 Scor 100
Compilator cpp Status done
Runda hash_excelenta Marime 1.19 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 666013

using namespace std;

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

vector < unsigned int > H[3 + MOD];
char S[10000010], W[25];

int Search(unsigned int value)
{
    int line = value % MOD;
    for (vector < unsigned int > :: iterator it = H[line].begin(); it != H[line].end(); ++ it)
        if (*it == value)
        {
            return 1;
        }
    return 0;
}

int main ()
{
    fin >> (S + 1);
    int N, M, sol = 0;
    unsigned int nr, pows[25];
    pows[1] = 1;
    for (int i = 2; i <= 21; ++ i) pows[i] = 3 *  pows[i-1];
    while (fin >> (W + 1) )
    {
        N = strlen (1 + W); nr = 0;
        for (int i = 1; i <= N; ++ i) nr += pows[i] * (W[i] - 'a');
        if (!Search (nr))
        {
            H[nr % MOD].push_back (nr);
        }
    }
    nr = 0;
    M = strlen (S + 1);
    for (int i = 1; i <= N; ++ i) nr += pows[i] * (S[i] - 'a');
    sol += Search (nr);
    for (int i = 1 + N ; i <= M; ++ i)
    {
        nr /= 3;
        nr += pows[N] * (S[i] - 'a');
        sol += Search (nr);
    }
    fout << sol << '\n';
    fout.close();
    return 0;
}