Cod sursa(job #1727362)

Utilizator cristina_borzaCristina Borza cristina_borza Data 10 iulie 2016 17:10:19
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <algorithm>
#include <fstream>
#include <cstring>
#include <set>
#include <map>

#define MOD 666013

using namespace std;

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

string cuv , prop;
unsigned int n , m , nr , sol;

vector <unsigned int> v[MOD + 5];

long long put[50];

bool caut(unsigned int val) {
    unsigned int qw = val % MOD;
    for (vector <unsigned int> :: iterator it = v[qw].begin(); it != v[qw].end(); ++it) {
        if (*it == val)
            return 1;
    }
    return 0;
}

int main() {
    f >> prop;
    m = prop.size();

    put[0] = 1;
    for (unsigned int i = 1; i <= 50; ++i) {
        put[i] = put[i - 1] * 3;
    }
    while (f >> cuv) {
        unsigned int hash1 = 0;
        n = cuv.size();

        for (unsigned int i = 0; i < n; ++i) {
            hash1 += (cuv[i] - 'a') * put[i];
        }

        if(caut(hash1) == 0)
            v[hash1 % MOD].push_back(hash1);
    }

    unsigned int hash1 = 0;
    for (unsigned int i = 0; i < n; ++i) {
         hash1 += (prop[i] - 'a') * put[i];
    }

    if (caut(hash1) == 1) {
       ++sol;
    }

    for (unsigned int i = n; i < m; ++i) {
        hash1 /= 3;
        hash1 += (prop[i] - 'a') * put[n - 1];

        if (caut(hash1) == 1) {
            ++sol;
        }
    }

    g << sol;
    return 0;
}