Cod sursa(job #1013067)

Utilizator deneoAdrian Craciun deneo Data 20 octombrie 2013 10:57:56
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 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 MOD2 = 1045279;
const int P = 27;

vector<int> h[MOD1];

int n;
string bigString, a;

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


int main() {
    fin >> bigString;

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

        for (int i = 0; i < a.size(); ++i) {
            hash1 = (hash1 * P + a[i]) % MOD1;
            hash2 = (hash2 * P + a[i]) % MOD2;
        }

        h[hash1].push_back(hash2);
    }

    int curHash1 = 0, curHash2 = 0;
    for (int i = 0; i < n; ++i) {
        curHash1 = (curHash1 * P + bigString[i]) % MOD1;
        curHash2 = (curHash2 * P + bigString[i]) % MOD2;
    }

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

    if (found(curHash1, curHash2))
        ++rez;

    for (int i = n; i < bigString.size(); ++i) {
        curHash1 = ((curHash1 - (bigString[i - n] * P1) % MOD1 + MOD1) * P + bigString[i]) % MOD1;
        curHash2 = ((curHash2 - (bigString[i - n] * P2) % MOD2 + MOD2) * P + bigString[i]) % MOD2;
        if (found(curHash1, curHash2))
            ++rez;
    }

    fout << rez;

    return 0;
}