Cod sursa(job #2670128)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 9 noiembrie 2020 09:16:43
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 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 mod1 = 2000000011;
    const int mod2 = 2000000203;

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

    unordered_set < int > hsubs1, hsubs2;

    for (auto it : subs)
    {
        int hsub1 = 0;
        int hsub2 = 0;
        for (int i=0; i<m; i++)
        {
            hsub1 = (1LL * hsub1 * base + it[i]) % mod1;
            hsub2 = (1LL * hsub2 * base + it[i]) % mod2;
            hsubs1.insert(hsub1);
            hsubs2.insert(hsub2);
        }
    }

    int p1 = 1;
    int p2 = 1;
    int hs1 = 0;
    int hs2 = 0;

    for (int i=0; i<m; i++)
    {
        hs1 = (1LL * hs1 * base + s[i]) % mod1;
        hs2 = (1LL * hs2 * base + s[i]) % mod1;
        if (i > 0)
        {
            p1 = (1LL * p1 * base) % mod1;
            p2 = (1LL * p2 * base) % mod2;
        }
    }

    string aux;

    if (hsubs1.count(hs1) && hsubs2.count(hs2))
        ans++;

    for (int i=m; i<n; i++)
    {
        hs1 = (((1LL * hs1 + mod1 - (1LL * p1 * s[i-m]) % mod1) * base) + s[i]) % mod1;
        hs2 = (((1LL * hs2 + mod2 - (1LL * p2 * s[i-m]) % mod2) * base) + s[i]) % mod2;
        if (hsubs1.count(hs1) && hsubs2.count(hs2))
            ans++;
    }
}

int main()
{
    f >> s;

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

    RabinKarp(s, subs, ans);

    g << ans;

    return 0;
}