Cod sursa(job #2670129)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 9 noiembrie 2020 09:17:29
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <unordered_set>
#include <vector>

using namespace std;

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

int ans;

string s, sub;

unordered_set < string > subs;

string subString(const string &s, int i1, int i2)
{
    string sub = "";

    for (int i=i1; i<=i2; i++)
        sub += s[i];

    return sub;
}

void RabinKarp(const string &s, const unordered_set < string > &subs, int &ans)
{
    const int base = 256;
    const int mod = 2000000011;

    int n = s.size();
    int m = (*subs.begin()).size();

    unordered_set < int > hsubs;

    for (auto it : subs)
    {
        int hsub = 0;
        for (int i=0; i<m; i++)
            hsub = (1LL * hsub * base + it[i]) % mod;

        hsubs.insert(hsub);
    }

    int p = 1;
    int hs = 0;

    for (int i=0; i<m; i++)
    {
        hs = (1LL * hs * base + s[i]) % mod;
        if (i > 0)
            p = (1LL * p * base) % mod;
    }

    string aux;

    if (hsubs.count(hs) && subs.count(subString(s, 0, m - 1)))
        ans++;

    for (int i=m; i<n; i++)
    {
        hs = (((1LL * hs + mod - (1LL * p * s[i-m]) % mod) * base) + s[i]) % mod;
        if (hsubs.count(hs) && subs.count(subString(s, i - m + 1, i)))
            ans++;
    }
}

int main()
{
    f >> s;

    while (f >> sub)
        subs.insert(sub);

    RabinKarp(s, subs, ans);

    g << ans;

    return 0;
}