Cod sursa(job #2099825)

Utilizator MaligMamaliga cu smantana Malig Data 4 ianuarie 2018 18:38:22
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 1e7 + 5;
const int lenMax = 1e7 + 5;
const int inf = 1e9 + 5;
const int base = 3;
const int mod = 100003;
using zint = int;

int N,M;
char str[NMax],cuv[NMax];
vector<int> h[mod];

bool check(uint);
void add(uint);

int main() {
    in>>(str);
    M = strlen(str);

    in>>cuv;
    int len = strlen(cuv);
    while (!in.fail()) {

        uint digest = 0;
        for (int k=0;k < len;++k) {
            digest = digest * base + (cuv[k] - 'a') * base;
        }

        add(digest);

        in>>cuv;
    }

    uint strDigest = 0,pw = 1;
    for (int k=0;k < len;++k) {
        strDigest = strDigest * base + (str[k] - 'a') * base;

        pw = pw * base;
    }

    int ans = 0;
    if (check(strDigest)) {
        ++ans;
        //pv(ans);
    }

    for (int j=len;j < M;++j) {
        strDigest = (strDigest - pw * (str[j-len] - 'a')) * base + (str[j] - 'a') * base;

        if (check(strDigest)) {
            ++ans;
        }
    }

    out<<ans<<'\n';

    in.close();out.close();
    return 0;
}
#define idx val%mod
bool check(uint val) {
    for (uint nr : h[idx]) {
        if (val == nr) {
            return true;
        }
    }

    return false;
}

void add(uint val) {
    h[idx].pb(val);
}