Cod sursa(job #1727333)

Utilizator cristina_borzaCristina Borza cristina_borza Data 10 iulie 2016 16:12:26
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <cstring>
#include <set>
#include <map>

#define MOD 1000000007
#define BASE 10

using namespace std;

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

char cuv[50] , prop[10000005];
long long n , m , nr;

map <long long , long long> mp;

int main() {
    f >> prop;
    m = strlen(prop);

    while (f >> cuv) {
        long long hash1 = 0;
        n = strlen(cuv);

        for (int i = 0; i < n; ++i) {
            hash1 = (hash1 * BASE + (cuv[i] - 'a' + 1)) % MOD;
        }

        mp[hash1] = 1;
    }

    long long P1 = 1, hash1 = 0;
    for (int i = 0; i < n; ++i) {
        hash1 = (hash1 * BASE + (prop[i] - 'a' + 1)) % MOD;
        if (i) {
            P1 = (BASE * P1) % MOD;
        }
    }

    if (mp[hash1] == 1) {
        mp[hash1] = 0;
        ++nr;
    }

    for (int i = n; i < m; ++i) {
        hash1 = ((hash1 - ((prop[i - n] - 'a' + 1) * P1) % MOD + MOD) * BASE + (prop[i] - 'a' + 1)) % MOD;

        if (mp[hash1] == 1) {
            mp[hash1] = 0;
            ++nr;
        }
    }

    g << nr;
    return 0;
}