Cvičení 15. 12. 2021: Stringy

Nový úkol: find_duplicates

• Deadline je "dva týdny modulo Vánoce". Tj., na posledním cviku.
• Úkol je atypický tím, že můžete používat cokoliv ze standardní knihovny vybraného jazyka.
• Taktéž můžete použít kód z templatů k předchozím úlohám, jen ho nezapomeňte vhodně "odcitovat".
• Cílem tak úplně není naimplementovat danou datovou strukturu, ale vyřešit problém. K čemuž budete potřebovat vhodnou datovou strukturu z přednášky.
• V době zadání úkolu už se probralo všechno, co ke splnění úkolu potřebujete.
• Máte striktní omezení na paměť, to by vám mohlo pomoct správně určit, kterou datovou strukturu potřebujete.
• Je v pořádku, že Python má méně paměti než C++. V Pythonu běží jen podmnožina testů, neb je moc pomalý.
• V úkolu velmi pravděpodobně budete muset chvíli ladit parametry. Začněte proto brzy!
• V Pythonu se může hodit bytearray , neb seznamy jsou extrémně prostorově neúsporné.

Př. 1: Hledání suffixovým polem

• Připomeňte si definici suffixového pole.
• Připomeňte si, jak funguje triviální hledání jehly P v kupce sena T pomocí suffixového pole, v čase \( \O(n\log(m)) \), \(n = |P|\), \(m = |T|\).
• Představte si, že umíte spočítat délky nejdelšího společného prefixu dvou řetězců x a y, LCP(x,y), v konstantním čase. Upravte triviální algoritmus tak, abyste dostali složitost \( \O(\log(m)) \).
  Hint: LCP vlastně porovnává dva řetězce. Krom nějakých okrajových situací by vám mělo stačit spočítat jen jedno LCP v každé fázi a vždy to je LCP mezi jehlou a nějakým suffixem sena.
• Teď se vrátíme do reality a zkusíme předchozí algoritmus upravit tak, aby fungoval i bez černé skříňky na LCP s černou skříňkou, která umí počítat LCP jen mezi suffixy sena, za cenu složitosti \( \O(n + \log(m)) \).
  Hint: Představte si, že jste uprostřed algoritmu a znáte vhodná LCP z minulých fází. Zkuste s jejich pomocí spočítat potřebné nové LCP tak, aby dohromady, přes celý běh algoritmu počítání všech LCP zabralo jen \( \O(n) \). K tomu se může hodit si všimnout, jak se hodnoty spočítaných LCP v průběhu algoritmu mění a co pro ně platí za invariant. Co všechno o pozici jehly v seně dokážete říct jen tím, že tato LCP porovnáte s vhodnými LCP některých suffixů sena? Rozeberte možné případy a všimněte si, že ve většině z nich vůbec nemusíte jehlu porovnávat s žádným sufixem. Pak už jen odargumentujte, že když už k porovnání dojde, tak dohromady přes celých algoritmus jich bude jen \( \O(n)\).
  Původní zadání a řešení bylo špatně. Správné řešení sepsal například pro své cvičení Lukáš Ondráček

Př 2.: Range minimum query

• Začněte s triviální strukturou, co umí odpovídat v konstantním čase a potřebuje kvadratický prostor.
• Zlepšete prostor (a čas předvýpočtu) na \(\O(n\log(n))\). Všimněte si, že není třeba předpočítat odpověď na každý dotaz, ale stačí vhodná podmnožina, ze které už každý jiný dotaz v konstantním čase poskládáte. Konktétně stačí jen dotazy určitých délek (ve složitosti je logaritmus, mrk, mrk) tak, aby vždy stačilo složit dva předpočítané dotazy na odpověď.
• Zkuste zkombinovat přechozí dvě konstrukce pomocí mikro-makro dekompozice. Pole si rozdělte na bloky velikosti B a vytvořte "zahuštěné" pole délky N/B. Pro bloky a zahuštěnou cestu vyberte vhodnout předchozí strukturu. Každý dotaz pak vhodně rozložte na dotaz na zahuštěnou cestu a dotaz na bloky. Zvolte B tak, abyste dostali celkem prostor (a složitost předpočítání) \( n\log(n)\). (To je sice stejný složitost je už máme, ale v následující části to zlepšíme.) Makro struktura by sama měla vycházet lineárně a, jak název napovídá, mikro struktury by měly být výrazně menší než původní pole.
• Nakonec zlepšíme mikro-makro dekompozici na lineární prostor. Tady vyžijeme toho, že sousední prvky se smí lišit nejvýš o jedničku. Pro pevné B, kolik různých takových polí délky B může existovat, pokud vždy začínáme nulou? Zvolte B tak, aby výsledek byl výrazně menší než n a na základě toho zkuste domyslet zbytek.