Úlohu vyřešíme metodou, která se často používá pro geometrické problémy. Představíme si přímku p rovnoběžnou s osou x, která se pohybuje ve směru osy y (od záporných čísel ke kladným – tomuto směru budeme říkat zezdola nahoru) a budeme simulovat průnik této přímky se zadanými úsečkami. Za tímto účelem budeme používat následující datové struktury:
Frontu událostí reprezentujeme haldou. Události porovnáváme dle jejich y-ových souřadnic, v případě shody podle pořadí v předešlém seznamu.
Na začátku je přímka p v -∞, tedy seznam S je prázdný a fronta U obsahuje horní a dolní konce všech úseček. Pro zjednodušení některých operací přidejme do S dvě falešné úsečky rovnoběžné s osou y, v -∞ a +∞ (nebo libovolných bodech ležících nalevo a napravo od všech ostatních úseček). V průběhu simulace odebíráme z U nejmenší událost a upravujeme S a U dle ní. Program končí ve chvíli, kdy přímka p dorazí do +∞, tedy když U je prázdná.
Vždy, když do S přidáme prvek, přidáme též do U událost průniku se sousedními úsečkami, pokud průnik existuje a leží nad p.
Popišme nyní detailněji, jak zpracováváme událost způsobenou úsečkou u. Události se stejnou y-ovou souřadnicí zpracováváme v tomto pořadí:
Je třeba ještě dořešit jeden technický detail: zaokrouhlovací chyby. Pokud by způsobily záměnu pořadí dvou událostí v U či dvou úseček v S, mohlo by to vést ke špatnému výsledku. Proto je nutné všechna porovnání dělat přesně. Toho lze dosáhnout více způsoby, jednou z možností je počítat souřadnice průsečíku jako zlomky.
Paměťová složitost našeho algoritmu je lineární – jak U, tak S vždy obsahují O(N) prvků. Jaká je jeho časová složitost? Nechť P je počet průsečíků úseček. Každá operace s U či S zabere čas O(logN). Spočítejme nyní počet těchto operací pro každou z událostí:
Počet událostí přidaných do U (včetně inicializace) je O(N+P) a počet odebraných událostí je tedy také O(N+P). Počet operací s S a U je omezen počtem událostí přidaných či odebraných z U a je O(N+P). Časová složitost proto je O((N+P)logN). Zmiňme, že existuje i rychlejší (a podstatně složitější) řešení s časovou složitostí O(NlogN+P).Viz B. Chazelle, H. Edelsbrunner: An Optimal Algorithm for Intersecting Line Segments in the Plane. Journal of the ACM 39, 1992.
Hledáme nejdelší souvislou podposloupnost čísel, jejichž součet je násobkem K, jinými slovy modulo K je roven nule. Pokud by ona podposloupnost měla začínat na začátku zadané posloupnosti, mohli bychom si jednoduše při čtení počítat průběžný součet modulo K od začátku až do aktuálního místa a ve chvíli, kdy by byl roven nule, si vždy poznamenat zatím nejlepší nalezený konec.
Zbývá se jen vypořádat s možností začínat na libovolném místě. Budeme postupovat obdobně – počítat si průběžně součet modulo K a pamatovat si zatím nejlepší nalezenou podposloupnost. Pokud jsme na pozici j a součet a1+a2+..+aj ≡ s mod K a zároveň známe nějaký index i≤j takový, že a1+a2+..+ai-1 ≡ s mod K, pak zřejmě ai+ai+1+..+aj ≡ 0 mod K. Je-li i zároveň nejmenší možné, lepší (tedy delší) podposloupnost končící na pozici j nemůže existovat a už se jen podíváme, zda je tato delší než nejlepší zatím nalezená.
A jak najít pro každé j nejmenší takový index i? Stačí si uvědomit, že na příslušné pozici jsme již byli a znali součet a1+a2+..+ai-1 mod K. Pokud tedy narazíme na index j takový, že a1+a2+..+aj-1 ≡ s mod K a a1+a2+..+aj'-1 ≡ s mod K pro všechna j'<j, tak si hodnotu j uložíme do pomocného pole velikosti K na index s; neexistenci indexu j'<j poznáme tak, že s-tá hodnota v uvažovaném pomocném poli dosud nebyla inicializována.
Algoritmus postupně prochází všech N prvků posloupnosti na vstupu a u každého stráví konstantně dlouhou dobu (test existence indexu j'<j, uložení do pomocného pole, výpočet rozdílu j-i a případné nahrazení nově nalezené optimální hodnoty). To trvá O(N), ovšem ještě potřebujeme inicializovat pomocné pole, takže celková časová složitost vyjde O(N+K). Pamatovat si budeme jen možné indexy i posloupností pro každý z K možných součtů s a několik dalších pomocných (konstantně velkých) údajů – paměťová složitost tedy bude O(K).
Tato úloha je podobná příkladu ve studijním textu, pouze místo výskytů dvou znaků počítá výskyty čtyř znaků. Můžeme o ní tedy uvažovat obdobně. Ihned se nabízí řešení pomocí čtyř zásobníků v lineárním čase: každé písmeno budeme ukládat do jeho zásobníku a na konci vybíráním po čtveřicích ověříme, že všechny zásobníky obsahovaly stejný počet písmen. Také můžeme jeden zásobník ušetřit tím, že si budeme pamatovat jen rozdíly počtů a-b, a-c a a-d.
Existuje ovšem i dvouzásobníkové řešení, které do jednoho zásobníku zakóduje všechna čtyři počítadla a druhý zásobník používá jako pomocný. To si předvedeme.
Nejprve si rozmysleme, jak bude fungovat jedno počítadlo. Počet budeme ukládat po číslicích, ovšem ve dvojkové soustavě. Chceme-li počítadlo zvýšit o jedničku, budeme postupovat podle klasického algoritmu pro sčítání čísel po cifrách. Číslo budeme procházet po číslicích zprava doleva (od nejnižšího řádu k nejvyššímu) a přepisovat přitom jedničky na nuly. Jakmile narazíme na první nulu, přepíšeme ji na jedničku a zastavíme se (například 110011+1=110100). Kdyby číslo skončilo dříve, domyslíme si vlevo od něj další nulu (111+1=0111+1=1000).
Jak tento postup naprogramovat pomocí zásobníků? Počítadlo uložíme na zásobník tak, aby nejpravější cifra ležela na vrcholu zásobníku. Můžeme tedy postupně odebírat jednotlivé číslice zprava, přepisovat je a odkládat do pomocného zásobníku. Až budeme hotovi, přesuneme je z pomocného zásobníku zpět do hlavního. Ve Stackalu to můžeme zapsat následovně:
Čtyři dvojková počítadla nyní můžeme uložit „přes sebe” na jeden zásobník. Každá položka zásobníku bude obsahovat čtyřbitové číslo, jehož i-tý bit bude představovat příslušnou cifru i-tého počítadla. Při zvyšování jednoho počítadla tedy budeme přepisovat jen příslušné bity a ostatní bity (patřící jiným počítadlům) zachováme.
K práci s bity se velice hodí bitové operace and a xor. Výraz a and b dává přirozené číslo, v jehož dvojkovém zápisu je na i-tém místě jednička právě tehdy, když je jednička na i-tém místě v číslech a i b. Podobně a xor b má jedničky tam, kde byla jednička buď v a, nebo v b, ale ne v obou. Proto a and 8 dává nulu právě tehdy, když je na čtvrté pozici zprava v čísle a nula (8 je dvojkově 1000), zatímco a xor 8 číslici na této pozici změní z nuly na jedničku a naopak. (Také bychom se bez těchto operací mohli obejít a čísla kódovat a dekódovat tabulkami, konec konců musíme ošetřit jen 16 možností, ale to by bylo poněkud pracné.)
Celý program tedy bude vypadat takto:
Program používá pouze dva zásobníky a spotřebuje paměť O(logN), protože každé číslo menší nebo rovné N má ve dvojkové soustavě nejvýše ⌊log2 N⌋+1 číslic. Délka čísla také omezuje počet opakování cyklu repeat pro každý znak, takže časová složitost není horší než O(NlogN). Ukážeme ovšem, že je lineární.
Rozbor stačí provést pro jedno počítadlo (tedy pro naši ukázkovou proceduru zvys), protože jednotlivá počítadla se navzájem neovlivňují a závěrečné porovnání trvá pouze O(logN). Navíc se stačí zaměřit na cyklus repeat v této proceduře, neboť přesouváním číslic z pomocného zásobníku v cyklu while zjevně trávíme nejvýše tolik času, jako když jsme je tam ukládali.
Uvažujme, co se stane, když proceduru zvys zavoláme N-krát po sobě na zpočátku nulové počítadlo. V každém průchodu cyklu repeat přepíšeme jednu číslici ve dvojkovém zápisu počítadla, tudíž časová složitost je přímo úměrná tomu, kolikrát došlo ke změně číslice.
Sledujme, jak se v průběhu výpočtu mění celkový počet jedniček v počítadle. Když v cyklu přepíšeme 0 na 1, jedna jednička přibude, v opačném případě jedna ubude. Navíc ihned po přepsání 0 na 1 se cyklus zastaví, takže se za celou dobu výpočtu počet jedniček zvýší nejvýše o N. Počet jedniček ovšem také nikdy neklesne pod nulu, takže operací, které ho snižují, může být rovněž nejvýše N. Všech operací je proto O(N).