Cod sursa(job #2831685)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 11 ianuarie 2022 21:22:30
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>
 
inline void Open(const std::string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}
 
const unsigned int MOD = (1 << 21) - 1;
 
std::vector <unsigned int> H[MOD];
 
char s[10000001], word[21];
 
unsigned int len, Len, hash, ans, offset = 1;
 
int InH(unsigned int hash) {
    unsigned int N = H[hash & MOD].size();
    for(unsigned int i = 0;i < N;i++)
        if(H[hash & MOD][i] == hash)
            return 1;
    return 0;
}
 
void addH(unsigned int hash) {
    if(!InH(hash))
        H[hash & MOD].emplace_back(hash);
}
 
void solve() {
    std::cin >> s;
    while(!std::cin.eof()) {
        std::cin >> word;
        len = strlen(word), hash = 0;
        for(unsigned int i = 0;i < len;i++)
            hash = (hash * 3 + (word[i] - 'a'));
        addH(hash);
    }
 
    hash = 0;
    for(unsigned int i = 0;i < len;i++) {
        hash = hash * 3 + (s[i] - 'a');
        offset *= 3;
    }
 
    offset /= 3, Len = strlen(s);
    ans += InH(hash);
 
    for(int i = len;i < Len;i++) {
        hash = (hash - offset * (s[i - len] - 'a')) * 3 + (s[i] - 'a');
        ans += InH(hash);
    }
 
    std::cout << ans;
}
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    Open("abc2");
 
    int T = 1;
    for(;T;T--) {
        solve();
    }
 
    return 0;
}