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
–
#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;
}