Szczegółowe omówienie zadania Repeating Substring:

Link do powyższego omówienia zadania Repeating Substring: https://youtu.be/dfpERcmogNM?t=1504
Link do treści zadania Repeating Substring: https://cses.fi/problemset/task/2106/

Zadanie Repeating Substring 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 "Repeating Substring", 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 = 1e5 + 7;
const int P = 313;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;

pair<int, int> hash_pref[MAXN];
pair<int, int> pow_P[MAXN];

pair<int, int> get_hash(int l, int r, int n)
{
    pair<int, int> h = {
        (hash_pref[r].first - hash_pref[l - 1].first + MOD1) % MOD1,
        (hash_pref[r].second - hash_pref[l - 1].second + MOD2) % MOD2};
    return {((ll)h.first * pow_P[n - l].first) % MOD1,
            ((ll)h.second * pow_P[n - l].second) % MOD2};
}

// zwraca indeks drugiego wystąpienia słowa
// lub -1 jeżeli żadne słowo długości d nie występuje dwukrotnie
int check_length(int d, int n)
{
    if (d == 0)
    	return 0;
    set<pair<int, int>> prev_hash;
    for (int i = 1; i <= n - d + 1; ++i) {
    	// h = H(s[i...i+d-1])
        pair<int, int> h = get_hash(i, i + d - 1, n);
        if (prev_hash.find(h) != prev_hash.end())
        	return i;
        prev_hash.insert(h);
    }
    return -1;
}

int BS(int lo, int hi, int n)
{
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (check_length(mid, n) == -1)
            hi = mid - 1;
        else
            lo = mid;
    }
    return lo;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;
    int n = s.size();
    pow_P[0] = {1, 1};
    for (int i = 1; i <= n; ++i) {
        pow_P[i] = {((ll)pow_P[i - 1].first * P) % MOD1,
                    ((ll)pow_P[i - 1].second * P) % MOD2};
    }
    for (int i = 0; i < n; ++i) {
        hash_pref[i + 1] = {
            ((ll)hash_pref[i].first + (ll)pow_P[i].first * s[i]) % MOD1,
            ((ll)hash_pref[i].second + (ll)pow_P[i].second * s[i]) % MOD2};
    }

    int d = BS(0, n-1, n);
    if (d == 0) {
        cout << "-1\n";
    } else {
        int ind = check_length(d, n);
        // wypisz s[ind..ind+d-1]
        for (int i = ind; i < ind + d; ++i)
        	cout << s[i - 1];
        cout << '\n';
    }
    return 0;
}

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