Cod sursa(job #1054350)

Utilizator costinbanuCostin Banu costinbanu Data 13 decembrie 2013 19:13:28
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef vector<unsigned> ht;
typedef ht::iterator it;

const unsigned MOD = 99991;

string text, word;
ht h[MOD + 2];

unsigned pow(unsigned exp) {
    if (exp > 0) return 3u * pow(exp - 1u);
    else return 1;
}

bool find(unsigned val){
    bool ok = 0;
    for(it i = h[val % MOD].begin(); i != h[val % MOD].end() && !ok; i++)
        ok = (*i == val);
    return ok;
}

int main() {
    ifstream f("abc2.in");
    ofstream g("abc2.out");
    f >> text >> word;
    unsigned nr = 0, n = word.size(), val, maxpow = pow(n - 1);
    do {
        val = 0;
        for (int i = 0; i < word.size(); i++)
            val = val * 3u + (word[i] - 'a');
        h[val % MOD].push_back(val);
        f >> word;
    } while (!f.eof());
    for (int i = 0; i < n; i++)
        val = val * 3u + text[i] - 'a';
    nr += find(val);
    for (int i = n; i < text.size(); i++) {
        val -= maxpow * (text[i - n] - 'a');
        val = val * 3u + text[i] - 'a';
        nr += find(val);
    }
    g << nr;
    f.close();
    g.close();
    return 0;
}