Cod sursa(job #2767794)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 7 august 2021 18:36:46
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <string>
#include <vector>
#define MOD 10003
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
string s1, s2;
unsigned int N, M, i ,j, sol;
unsigned long long cod, p;
vector <unsigned int> Map[MOD];
inline bool isThere(unsigned long long x) {
    unsigned long long key = 1ULL * x % MOD;
    for (int i = 0; i < Map[key].size(); ++i)
        if ( Map[key][i] == x ) return 1;
    return 0;
}
inline void Push(unsigned long long x){
    if(!isThere(x)) {
        unsigned long long key = 1ULL * x % MOD;
        Map[key].push_back(x);
    }
}
int main() {
    f >> s1;
    f >> s2;
    N = s1.size();
    M = s2.size();
    cod = 0;
    for (i = 0; i < M; ++i) {
        cod = cod * 3 + (s2[i] - 'a') ;
    }
    Push(cod) ;
    while (f >> s2) {
        cod = 0;
        for (i = 0; i < M; ++i) {
            cod = cod * 3 + (s2[i] - 'a');
        }
        Push(cod);
    }
    cod = 0;
    p = 1;
    for (i = 0; i < M; ++i) {
        cod = cod * 3 + (s1[i] - 'a');
    }
    sol = 0;
    for (i = 1; i < M; ++i)
        p *= 3;
    if (isThere(cod)) ++sol;
    for (i = M; i < N; ++i) {
        cod = 1ULL * cod - p * 1ULL * (s1[i - M] - 'a' )   ;
        cod = 1ULL * cod * 3 + (s1[i] - 'a');
        if ( isThere(cod)) ++sol;
    }
    g << sol;
    return 0;
}