Szczegółowe omówienie zadania Caps Lock:

Link do powyższego omówienia zadania Caps Lock: https://youtu.be/WZojS2DHEK0?t=1623
Link do treści zadania Caps Lock: https://szkopul.edu.pl/problemset/problem/xss1BbTCqSIb-udUi6NnHb4P/site

Zadanie Caps Lock wykorzystuje pokazuje czym są hashe: https://youtu.be/WZojS2DHEK0?t=1623
Gdzie wykorzystuje się hashe? https://youtu.be/WZojS2DHEK0?t=164

Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia Olimpiada Informatyczna POZIOM II: https://oki.org.pl/olimpiada-informatyczna-poziom-ii/
Wszystkie zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

–
Kod C++ programu "Caps Lock", który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 7;
const int P = 199;
const int MOD = 1e9 + 7;

int pow_P[MAXN];
int H[MAXN];

int get_hash(int l, int r, int n) {
    ++l;
    ++r;
    int res = (H[r] - H[l - 1] + MOD) % MOD;
    return ((ll)res * pow_P[n - l + 1]) % MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string text;
    cin >> text;
    string pattern;
    cin >> pattern;
    int n = text.size();
    int m = pattern.size();

    // obliczanie poteg liczby *P* modulo *MOD*
    pow_P[0] = 1;
    for (int i = 1; i <= n; ++i)
    	pow_P[i] = ((ll)pow_P[i - 1] * P) % MOD;

    // obliczanie hashu slowa *pattern*
    int patternH = 0;
    for (int i = 0; i < m; ++i)
        patternH = ((ll)patternH + (ll)pow_P[i] * pattern[i]) % MOD;
    patternH = ((ll)patternH * pow_P[n]) % MOD;

    // obliczanie hashy dla kazdego prefiksu słowa *text*
    H[0] = 0;
    for (int i = 0; i < n; ++i)
        H[i + 1] = ((ll)H[i] + (ll)pow_P[i] * text[i]) % MOD;

    string ans = text;
    for (int i = m - 1; i < n; ++i) {
        // sprawdzam, czy slowo *text[i-m+1...i]* jest rowne *pattern*
        if (get_hash(i - m + 1, i, n) == patternH) {
            // jezeli tak, to zamieniam na wielkie litery
            for (int j = 0; j < m; ++j) {
                if (ans[i - j] <= 'Z') break;
                ans[i - j] -= 32;  // 'a' - 'A'
            }
        }
    }
    cout << ans << '\n';
    return 0;
}