Cod sursa(job #3318149)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 27 octombrie 2025 12:28:52
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 10000005;
const long long BASE1 = 131, MOD1 = 1000000007;
const long long BASE2 = 137, MOD2 = 1000000009;
const char HASHER = 'a' - 1;

char TEXT[NMAX], WORD[25];
long long powers1[25], powers2[25];

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

void PrecomputePowers(int L) {
    powers1[0] = powers2[0] = 1;
    for (int i = 1; i <= L; i++) {
        powers1[i] = (powers1[i-1] * BASE1) % MOD1;
        powers2[i] = (powers2[i-1] * BASE2) % MOD2;
    }
}

pair<long long,long long> HashString(const char s[], int L) {
    long long h1=0, h2=0;
    for(int i=0;i<L;i++){
        h1 = (h1*BASE1 + (s[i]-HASHER)) % MOD1;
        h2 = (h2*BASE2 + (s[i]-HASHER)) % MOD2;
    }
    return {h1,h2};
}

uint64_t Combine(pair<long long,long long> h){
    return ((uint64_t)h.first << 32) | h.second;
}

unordered_set<uint64_t> BuildDictionary(vector<string> &words, int L){
    unordered_set<uint64_t> dict;
    dict.reserve(words.size()*2);
    dict.max_load_factor(0.25);
    for(auto &w: words){
        if((int)w.size()!=L) continue;
        dict.insert(Combine(HashString(w.c_str(),L)));
    }
    return dict;
}

pair<long long,long long> UpdateWindow(pair<long long,long long> h, char out, char in, int L){
    h.first = (h.first - (out-HASHER)*powers1[L-1]%MOD1 + MOD1)%MOD1;
    h.first = (h.first*BASE1 + (in-HASHER))%MOD1;
    h.second = (h.second - (out-HASHER)*powers2[L-1]%MOD2 + MOD2)%MOD2;
    h.second = (h.second*BASE2 + (in-HASHER))%MOD2;
    return h;
}

long long CountPositions(char text[], int n, int L, unordered_set<uint64_t> &dict){
    auto h = HashString(text,L);
    uint64_t combined = Combine(h);
    long long count = dict.count(combined) ? 1 : 0;
    for(int i=L;i<n;i++){
        h = UpdateWindow(h,text[i-L],text[i],L);
        combined = Combine(h);
        if(dict.count(combined)) count++;
    }
    return count;
}

int main(){
    ios::sync_with_stdio(false);
    fin.tie(nullptr);

    fin >> TEXT;
    int n = strlen(TEXT);

    vector<string> words;
    while(fin >> WORD) words.push_back(string(WORD));

    if(words.empty() || n==0){
        fout << 0 << "\n";
        return 0;
    }

    int L = words[0].size();
    if(n<L){
        fout << 0 << "\n";
        return 0;
    }

    PrecomputePowers(L);
    unordered_set<uint64_t> dict = BuildDictionary(words,L);
    long long result = CountPositions(TEXT,n,L,dict);
    fout << result << "\n";
    return 0;
}