Cod sursa(job #2432752)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 24 iunie 2019 22:50:18
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;

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

const int BASE = 73;
const int MOD = 666013;

int getHashCode(string str) {
    int h = 0;
    for (int i = 0; i < (int) str.size(); i++)
        h = (h * BASE + str[i]) % MOD;
    return h;
}

int pow(int x, int n) {
    if (!n)
        return 1;
    if (n & 1)
        return x * pow(x * x % MOD, n >> 1) % MOD;
    return pow(x * x % MOD, n >> 1);
}

int main() {
    string str; fin >> str;
    set<int> patterns; int len = 0;

    string pattern;
    while (fin >> pattern) {
        len = pattern.size();
        patterns.insert(getHashCode(pattern));
    }

    int h = getHashCode(str.substr(0, len));
    int sol = (patterns.find(h) != patterns.end());

    int pwr = pow(BASE, len - 1);
    for (int i = len; i < (int) str.size(); i++) {
        h = (((h - str[i - len] * pwr) % MOD + MOD) * BASE + str[i]) % MOD;
        sol += (patterns.find(h) != patterns.end());
    }
    fout << sol << '\n';

    fout.close();
    return 0;
}