5. Interpunkčné párovanie vzorové riešenie

4
{[{]}
[(){}
[(([]())]
[

1
3
6
1

Keďže z reťazca bola podľa zadania odstránená práve jedna zátvorka, chceme zistiť, aká. Nájsť chýbajúcu zátvorku vieme tak, že jednoducho prejdeme celý reťazec a spočítame výskyty jednotlivých zátvoriek. Typ zátvorky, ktorého početnosť v reťazci je o \(1\) menšia ako početnosť jeho párového typu, chýba. Okay, inými slovami, ak sme zistili, že je v reťazci, napríklad, \(n\times\) ( a \((n - 1)\times\) ), vieme, že chýba ).

Pomalé riešenie a overenie správnosti uzátvorkovania reťazca

Dobre, máme chýbajúcu zátvorku. Čo s ňou? Skúsme ju vložiť na všetky možné pozície a spočítajme, pri koľkých týchto pokusoch vznikne správne uzátvorkovaný reťazec. Ako ale vieme zistiť, či je reťazec správne uzátvorkovaný?

Použijeme zásobníkový automat. Každá otváracia zátvorka, napr. (, musí mať niekde vpravo od seba svoju zatváraciu, ). A to nie len-tak niekde. Teda, zamerajme sa skôr na to, čo musí platiť v intervale medzi týmto párom zátvoriek.

Musí sa tu nachádzať správne uzátvorkovaný (korektný) podreťazec alebo viac takýchto podreťazcov vedľa seba. Napríklad: ( {[]()} [] ). Medzi vonkajšími () sa nachádzajú dva korektné podreťazce: {[]()} a [].
Z tohto sa nám už črtá akési rekurzívne pravidlo, že každý korektný podreťazec, ohraničený párom zátvoriek (v správnom smere), obsahuje \(0\) alebo viac korektných podreťazcov vedľa seba. Napríklad [] je korektný podreťazec, ktorý obsahuje \(0\) podreťazcov v sebe; a {[]()} obsahuje [](), atď.

Ako teda vieme použiť zásobníkový automat? Povedzme, že prechádzame reťazec po znakoch zľava. Ak nájdeme otváraciu zátvorku, pridáme si ju do zásobníka a ideme ďalej. Ak nájdeme zatváraciu zátvorku, musí to byť práve párová zátvorka k zátvorke na vrchu zásobnika. Ak to platí, otváraciu zátvorku zo zásobnika vyberieme. Znamená to, že uzátvára zátvorku, ktorá sa otvorila ako posledná a nebola ešte uzavretá. Nemôže sa stať, že sa otvorí, napr. ( a hneď za ňou sa zatvorí ]. Vtedy by bol reťazec nekorektný.

Napríklad: ( {[]()} [] ) - na začiatku sme našli prvú (, potom sme skontrolovali niekoľko ďalších párov, ktoré boli kompletné (otvorili sa a zatvorili bez toho, aby sa “pretínali”, napr. {[}], a teraz sme našli poslednú ), ktorá je zatváracia k tej prvej, čiže “uzátvára zátvorku, ktorá sa otvorila ako posledná z tých, čo ešte neboli uzavreté”. Z toho je jasné, že nás ten stred (podreťazec medzi krajnými zátvorkami) nezaujíma.

Takáto kontrola prejde celý reťazec iba raz. Vyberať z a vkladať do zásobnika vieme v konštantnom čase. Preto vieme povedať, že časová zložitosť jedného overenia reťazcu dĺžky \(n\) je \(O(n)\).

Pamätať si potrebujeme iba zásobník, ktorý plníme len zo vstupného reťazca, preto jeho veľkosť určite nepresiahne veľkosť vstupného reťazca, čo je rovnako \(O(n)\).

Správnosť stringu v tomto riešení ale overujeme pre každú možnú pozíciu chýbajúcej zátvorky, ktorých je \(n + 1\). To nám dokopy dáva časovú zložitosť \(O(n^2)\).

Dá sa to rýchlejšie? Pýtal by som sa, ak by sa nedalo?

Niečo lepšie

Naozaj musíme skúšať doplniť chýbajúcu zátvorku na všetky miesta v reťazci? Vieme nejako zistiť kam najskôr a kam najneskôr môžeme doplniť chýbajúcu zátvorku? Áno.

Skúsme zásobníkovým automatom overiť správnosť reťazca zo vstupu aj keď vieme, že je pokazený. Akú ďalšiu informáciu si z toho ale vieme vziať?

Na vstupe je toto: [(([]())]{}. Pustíme na to zásobníkový automat (popísaný vyššie). Ten sa zasekne na tretej zátvorke od konca, keďže na vrchu zásobníka je (, ale na vstupe sa nachádza ]. Má zmysel doplniť chýbajúcu zátvorku niekam za túto ]?

Uvedomme si: Ak doplníme chýbajúcu zátvorku hocikam za miesto zaseknutia, pri spustení automatu pre overenie sa automat zasekne znova na rovnakom mieste a k novo doplnenej zátvorke sa ani nedostane, lebo chybná časť reťazca zostala nezmenená. Týmto sme vlastne našli hranicu, pokiaľ má zmysel skúšať doplniť chýbajúcu zátvorku. Tak isto vieme spustiť automat aj z opačnej strany a zasekne sa na ( prvej z ľava.

Tým pádom nám zostalo [(_(_[_]_(_)_)_]{}, kde _ znázorňuje miesto, kam má zmysel skúsiť doplniť zátvorku. Teraz môžeme na každé _ skúsiť doplniť zátvorku a overiť korektnosť reťazca.

Je to určite zaujímavá myšlienka, no pri takomto použití je toto len jemná optimalizácia. Časová zložitosť tohto vylepšenia je aj tak stále \(O(n^2)\), takže sme veľmi potenciál týchto “hraníc” nevyužili. Ako teda túto informáciu využiť naplno?

Vzorové riešenie

Dokážeme zistiť, či zátvorku môžeme doplniť na dané miesto, bez toho, aby sme museli overiť korektnosť reťazca? HmÁno!

Dobre, zásobníkovým automatom sme zistili, kde najskôr a kde najnekôr, mohla vzniknút chyba. Chyba znamená, že nejaká zátvorka sa otvorila a nezatvorila. Je to jasné? Pri prechode automatom sme narazili na miesto, kde sme chceli zavrieť nejakú zátvorku, ale zistili sme, že ešte iná nebola zavretá, a tým pádom sa to celé pokazilo. (Ak chýba otváracia zátvorka, vieme rovnakú úvahu aplikovať na reťazec z opačnej strany)

Ako vieme tento pokazený reťazec opraviť? Zavrieme túto nezatvorenú zátvorku. To sa zdá byť celkom jednoduché a toto zdanie nie je ďaleko od pravdy.

Ako by sme “zavreli” zátvorku? (Spomeňme si na štvrtý odsek tohto vzoráku) Doplníme zatváraciu zátvorku niekam vpravo od prvej otvorenej v nájdenom intervale (prvá zátvorka bude určite práve opačná k chýbajúcej) tak, aby sa v ich vnútri nenachádzalo nič alebo nejaký korektný podreťazec. Ak by sme do vnútra zátvoriek uzaverli nekorektný podreťazec, celý reťazec by bol nekorektný a preto by daná pozícia doplnenej zátvorky nepripadala do úvahy.

Napríklad, zostal nám interval [() a chýba nám v reťazci ]. Môžeme ju doplniť takto: []() alebo takto: [()], ale nie takto: [(]). Ak by bol interval [[()], máme \(4\) možnosti, kam dať chýbajúcu ]: [][()], [[]()], [[()]] a [[()]].

Všimnime si, že poslednú a predposlednú možnosť rátame ako dve, aj keď v konečnom výsledku vyzerajú rovnako. To preto, lebo nás zaujíma, kam dáme chýbajúcu zátvorku, nie koľko rôznych reťazcov môže vzniknúť. Chápeme, že všetky zátvorky sú unikátne a je teda rozdiel, či doplníme chýbajúcu zátvorku na posledné alebo predposledné miesto.

Je tak zrejmé, že zátvorku chceme dpolniť, buď hneď za jej opačnú (ak tá nie je vo vnútri iných zátvoriek, čo znamená, že je tento podreťazec korektný a pridaním ďalšej zátvorky by sa určite pokazil), alebo medzi nimi nechať nejaký “uzavretý” korektný reťazec/reťazce.

“Uzavretý” korektný reťazec znamená, že ho obkolesujú zátvorky iného typu, ako chýbajúca. To znamená, že doň nemôžeme nič vložiť, lebo by sme ho pokazili.

Poslednou časťou skladačky je tak identifikovanie “uzavretých” korektných podreťazcov v skúmanom intervale. Vieme ľahko zistiť, že takýto podreťazec začína tým, že prečítame otváraciu zátvorku iného typu, akého je chýbajúca. Ako potom zistiť, pokiaľ až tento uzavretý podreťazec siaha? Vieme zase použiť zásobníkový automat Vieme, že podreťazec je korektný. Tým pádom končí, keď sa zásobník automatu vyprázdni.

Takto dokážeme jedným prechodom intervalu nájsť, a teda aj spočítať, miesta, kam je možné doplniť chýbajúcu zátvorku.

Zložitosti

Pre nájdenie hraníc intervalu potrebujeme pustiť zásobníkové automaty z oboch strán. Vkladanie a vyberanie zo zásobníka má konštantnú časovú zložitosť, takže časová zložitosť nájdenia hraníc pri \(n\) znakoch je \(O(n)\). Nájdenie a spočítanie vhodných miest trvá jeden prechod nájdeneho intervalu, čo je tiež \(O(n)\). Preto aj výsledná časová zložitosť je \(O(n)\).

Potrebujeme si zjavne pamätať celý reťazec, aby sme ho mohli prejsť z oboch strán. Okrem toho si niekedy pamätáme obsah nejakého zásobníka, ktorý plníme len zo vstupného reťazca, preto jeho veľkosť určite nepresiahne veľkosť vstupného reťazca. Preto hovoríme \(O(n)\).

Keďže máme \(t\) reťazcov o dĺžkach \(n_1, n_2\dots n_t\), vieme časovú zložitosť odhadnúť pomocou sumy: \(O(\sum_{i=1}^t n_i)\) a pamäťovú pomocou maxima: \(O(MAX(N))\), kde \(N = \{n_1, n_2\dots n_t\}\).