Cvičení 15. 12. 2021: Stringy

\( \def\H{\mathcal{H}} \def\U{\mathcal{U}} \def\B{\mathcal{B}} \def\O{\mathcal{O}} \)

Nový úkol: find_duplicates

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

Př 2.: Range minimum query

Při práci se suffixovými poli (a nejen těmi) se často hodí umět rychle odpovídat na dotazy "Jaké je minimum tohoto intervalu?". Máme tedy nějaké pole n čísel A a chceme si předpočítat nějakou datovou strukturu, která nám umožní odpovídat dotazy "kolik je min(A[i:j])?".
Náš ultimátní cíl je konstantní čas na dotaz a lineární prostor pro předpočítanou strukturu. Pro zjednodušení budeme předpokládat, že \(|A[i] - A[i+1]| \le 1\).
Kompletní řešení můžete najít např. zde (druhá polovina), či zde (strana 10, řešení úlohy 4.2).