Cod sursa(job #1013079)

Utilizator deneoAdrian Craciun deneo Data 20 octombrie 2013 11:18:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

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

const int MOD1 = 67891;
const int P = 3;

vector<int> h[MOD1];

int n;
string bigString, a;

bool found (int hash1) {
    for (int i = 0; i < h[hash1 % MOD1].size(); ++i)
        if (h[hash1 % MOD1][i] == hash1)
            return 1;
    return 0;
}


int main() {
    fin >> bigString;

    while (fin >> a) {
        unsigned int hash1 = 0;
        n = a.size();

        for (int i = 0; i < a.size(); ++i)
            hash1 = (hash1 * P + a[i] - 'a');

        h[hash1 % MOD1].push_back(hash1);
    }

    unsigned int curHash1 = 0;
    for (int i = 0; i < n; ++i)
        curHash1 = (curHash1 * P + bigString[i] - 'a');

    int rez = 0, P1 = 1;
    for (int i = 1; i < n; ++i)
        P1 = (P1 * P) % MOD1;

    if (found(curHash1))
        ++rez;

    for (int i = n; i < bigString.size(); ++i) {
        curHash1 -= P1 * (bigString[i - n] - 'a');
        curHash1 = curHash1 * P + bigString[i] - 'a';
        if (found(curHash1))
            ++rez;
    }

    fout << rez;

    return 0;
}