Cod sursa(job #1782827)

Utilizator zacuscaAlex Iordache zacusca Data 18 octombrie 2016 16:23:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda hash_excelenta Marime 1.15 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 1000003
 
using namespace std;
 
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
 
vector < unsigned int > H[3 + MOD];
char S[10010010], W[100];
 
int Search(int value)
{
    int line = value % MOD;
    for (int i = 0; i < H[line].size(); ++ i)
        if (H[line][i] == value)
        {
            return 1;
        }
    return 0;
}
 
int main ()
{
    fin >> 1 + S;
 
    int N, M, sol = 0;
    unsigned int nr, pows[100];
    pows[1] = 1;
    for (int i = 2; i <= 20; ++ i) pows[i] = 3 *  pows[i-1];
    while (fin >> 1 + W)
    {
        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 (1 + S);
    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;
}