Zadanie
Ďaleko na severe, hlboko v Británii, v obrovskej knižnici ukrytej v útrobách podzemnej kamennej jaskyne už celé stáročia pracuje čarodejník Merlin. Merlin má na starosti veľké množstvo písomností z čarodejníckej literatúry, ktorá je pre ostatných čarodejníkov veľmi dôležitá.
Títo čarodejníci za ním najčastejšie chodia s troma typmi dotazov:
- Sú tieto dve kúzla vo Veľkom zvitku rovnaké?
- Nachádza sa v tejto knihe tento reťazec písmen?
- Koľko many potrebujem na použitie tohto kúzla?
Merlin potrebuje čo najrýchlejšie odpovedať na tieto otázky, aby sa mohol venovať aj iným prospešným činnostiam.
Úloha
Merlin nevie veľmi rýchlo pracovať s textom a písmenami. Keď chce napríklad porovnať, či sú dva reťazce písmen rovnaké, postupne prechádza oba reťazce znak po znaku, až kým nenájde miesto, v ktorom sa líšia, alebo nepríde na koniec reťazcov. Ak napríklad porovnáva, či sú “abrakadabra” a “abrakazebra” rovnaké, porovnáva postupne “a”=“a”, “b”=“b”, “r”=“r”, “a”=“a”, a tak ďalej. Postupne overí, že prvých šesť znakov je rovnakých a potom na siedmom znaku má jeden reťazec písmeno “d” a druhý “z”. Tieto reťazce teda nie sú také isté.
Overiť, že “athraighanboscaadhmaidseoinachloch” je to isté ako “athraighanboscaadhmaidseoinachloch” mu trvá 34 krokov. Pokiaľ by sa nejaké reťazce zhodovali na prvých dvetisíc znakoch a odlišovali sa na dvetisíc prvom, trvalo by mu zistiť, že sú rôzne, 2001 krokov. To je príliš dlho.
Podobne overiť, či sa nejaký reťazec nachádza v nejakej knihe je ťažké. Napríklad aby zistil, či sa \(R =\) “ababababac” nachádza v \(K =\) “abababababababababab”, postupoval Merlin tak, že postupne overoval: Je prvých 10 znakov K rovnakých ako R? Sú znaky 2 až 11 v K rovnaké ako R? Sú znaky 3 až 12 v K rovnaké ako R? Sú znaky 4 až 13 v K rovnaké ako R? Sú znaky 5 až 14 v K rovnaké ako R? A tak ďalej až po: Sú znaky 11 až 20 v K rovnaké ako R?
Na to potreboval \(10 + 1 + 10 + 1 + 10 + 1 + 10 + 1 + 10 + 1 = 55\)-krát porovnať nejaké dva znaky (10 porovnaní v prípade, že dané písmená v \(K\) tvorili reťazec "ababababa" a až potom prišlo na nezhodu s písmenom "c", 1 porovnanie v prípade, že postupnosť v \(K\) začínala písmenom "b" a teda chybu objavil hneď pri prvom porovnaní). Overiť, či sa 1000 znakový reťazec nachádza v milión znakov dlhej knihe môže trvať skoro až miliardu krokov. A to je dosť veľa.
Na druhú stranu, ako správny čarodejník, Merlin dokáže rýchlo pracovať s číslami. Sčítať, vynásobiť či porovnať dve čísla mu trvá jeden krok bez ohľadu na to, aké sú čísla veľké. Podobne jednoduché operácie s jedným alebo dvoma číslami, vie tiež robiť takto rýchlo, ale keď je čísel viac, nevie to spraviť naraz. Sčítať \(n\) čísel by mu stále trvalo \(n-1\) krokov.
Často, keď Merlin pracuje s reťazcami, prevedie si ich na zoznam čísel. Písmena abecedy si očísluje od a=1 až po z=26 a potom reťazec písmen je zoznam k nim prislúchajúcich čísel. Napríklad “abrakadabra” = 1, 2, 18, 1 11, 1, 4, 1, 2, 18, 1.
Nasledovné pojmy súčet a magické číslo budeme používať v podúlohách, tak si ich teraz popíšme.
Súčet nejakého reťazca je súčet jeho písmen prevedených na čísla. Napríklad súčet “abrakadabra”, je \(S\)(abrakadabra) = \(1+2+18+1+11+1+4+1+2+18+1 = 60\).
Magickú hodnotu nejakého reťazca vypočítame nasledovne: Opäť písmenám priradíme čísla a=1 až z=26, ale tentokrát tieto písmená pred sčítaním ešte niečim vynásobíme. Posledný znak vynásobíme jednotkou, predposledný číslom 47, predpredposledný číslom 47 krát 47. \(i\)-ty znak od konca (začínajúc od \(i=0\)) \(i\) krát vynásobíme číslom 47.
Magická hodnota reťazca “zebra” je \(M\)(zebra) \(= 47^4\cdot 26 + 47^3\cdot 5 + 47^2\cdot 2 + 47\cdot 18 + 1\cdot 1 =\) \(4879681\cdot 26 + 103823\cdot 5 + 2209\cdot 2 + 47\cdot 18 + 1 =\) \(126871706 + 519115 + 4418 + 846 + 1 =\) \(127396086\) (Zápis \(a^k\) voláme umocňovanie a je to zápis pre vynásobenie čísla \(a\) \(k\)-krát. Napríklad \(47^4 = 47\cdot 47\cdot 47\cdot 47 = 4879681\))
Podobne magická hodnota reťazca “abrakadabra” je \(M\)(abrakadabra) \(= 55266621785409182\).
Vypočítať súčet či magické číslo nejakého reťazca dlhého \(\ell\) zaberie Merlinovi rádovo \(\ell\) krokov.
Podúloha a – úvod
V Merlinovom Veľkom zvitku sú postupne napísané všakovaké kúzla, v poradí v akom ich jeho predkovia objavili. Každé kúzlo je reťazec malých písmen anglickej abecedy. Mohlo sa stať, že nejaké kúzlo bolo objavené viackrát, a tak sa môže vo zvitku nachádzať rovnaké kúzlo opakovane. Ostatní čarodejníci pravidelne Merlina navštevujú a pýtajú sa ho otázky tvaru: “Je \(i\)-te kúzlo a \(j\)-te kúzlo vo Veľkom zvitku rovnaké?”
Merlin tiež vlastní Malý zvitok, ktorý si už dávnejšie vyrobil. Na \(i\)-tom riadku tohto zvitku je napísaný súčet \(i\)-teho kúzla a tiež jeho magická hodnota, ktoré spočítal postupom uvedeným vyššie.
Merlin teraz rozmýšľa, či by nedokázal použiť Malý zvitok na to,
aby dokázal by na otázky čarodejníkom rýchlo a okamžite, bez toho aby kúzla porovnával pracne, znak po znaku.
Podúloha a – (4 body)
Nájdite dve rôzne kúzla, ktoré majú rovnaký súčet, alebo stručne ukážte, prečo také kúzla neexistujú.
Nájdite dve rôzne kúzla, ktoré majú rovnakú magickú hodnotu, alebo stručne ukážte, prečo také neexistujú.
Stručne popíšte postup, ako Merlin môže odpovedať na otázky ostatných čarodejníkov, len pomocou Malého zvitku. Napríklad, čo s čím má Merlin porovnať a ako má vyhodnotiť výsledok, ak chce zistiť, či sú \(i\)-te a \(j\)-te kúzlo vo Veľkom zvitku rovnaké.
Podúlohy b a c. – úvod
Niektorí čarodejníci nevedia čítať. A tak chodia za Merlinom, donesú mu knihu dlhú \(k\) znakov a spýtajú sa, či sa v knihe nachádza nejaký konkrétny reťazec dlhý \(r\) znakov.
Napríklad “braka”, “dabra” aj “a” sa nachádzajú v “abrakadabra”, ale “zebra” ani “aaa” sa tam nenachádzajú.
Podúloha b (3 body)
Kráľ Pendragon mal rád čísla, pravidelnosť a rád písal knihy. Všetky jeho knihy majú presne milión znakov (malých písmen anglickej abecedy) a majú zaujímavú vlastnosť: Každý úsek 1000 znakov v nej má iný súčet.
Navrhnite postup, ako efektívne zistiť, či sa zadaný 1000 znakový reťazec nachádza v danej knihe napísanej kráľom Pendragonom.
Keď hovoríme “efektívne” máme tým namysli, že tento postup netrvá príliš dlho. Skúste nájsť postup, ktorý potrebuje niekoľko miliónov krokov, prípadne zopár desiatok miliónov krokov, nie však miliardu.
Bežné matematické operácie, ako previesť písmeno na číslo, sčítať dve čísla, porovnať dve čísla, vynásobiť dve čísla trvajú jeden krok. Avšak už sčítať \(n\) čísel, alebo pozrieť sa na \(n\) hodnôt trvá \(n\) krokov.
Podúloha c (3 body)
Navrhnite spôsob, ako efektívne zistiť, či sa zadaný reťazec \(R\) dĺžky \(r\) nachádza v zadanom reťazci \(K\) dĺžky \(k\).
Poznámky: O reťazci \(K\) už nemáte žiadne záruky, ako v predošlej podúlohe. Možno sa vám bude lepšie spisovať riešenie, ak budete používať označenie \(K_i\) resp. \(K[i]\) pre \(i\)-ty znak knihy a \(R_j\) resp. \(R[j]\) pre \(j\)-ty znak hľadaného reťazca. Rada: zamyslite sa, či sa dajú použiť magické čísla popísané vyššie v zadaní.
Podúloha d. (5 bodov)
Každé kúzlo potrebuje na vyčarovanie toľko many, koľko jeho začiatkov (prvých niekoľko písmen) je zároveň aj jeho koncom (posledných niekoľko písmen). Napríklad kúzlo “abrakadabra” spotrebuje 3 many, lebo “a”, “abra” a “abrakadabra” sú všetko začiatky, ktoré sú zároveň aj konce. Kúzlo “aaaaa” spotrebuje 5 many a “ttottogttottogttottogtt” tiež 5 many (začiatky a zároveň konce sú “t”, “tt”, “ttottogtt”, “ttottogttottogtt” a celé kúzlo). Kúzlo “abracaz” potrebuje len jednu manu, lebo žiaden začiatok okrem celého kúzla nie je aj koncom.
Navrhnite postup, ktorý pre dané kúzlo čo najrýchlejšie vypočíta, koľko many potrebujeme na jeho vyčarovanie. Váš postup by mal použiť rádovo toľko krokov, aká je dĺžka kúzla.
Podúloha a.
Pri sčítavaní čísel nezáleží, v akom poradí sú tieto čísla: \(a + b = b + a\) (hovoríme, že sčítanie je komutatívna operácia). Preto keď v kúzle preusporiadame písmená, nezmení sa ich súčet. Príklady rôznych kúzel s rovnakým súčtom sú ahoj, hoja, joha, ale aj ahoj a bgoj.
S magickou hodnotou je to inak. Nedajú sa nájsť dve rôzne kúzla, ktoré by mali rovnakú magickú hodnotu. Predstavme si, čo by sa stalo, keby takéto kúzla existovali. Nájdime prvú pozíciu od konca, na ktorej sa písmena kúzel líšia. Označme si pozíciu týchto písmen od konca \(k\). Rozdelme si magickú hodnotu kúzel na tri časti
- A = tá, do ktorej sa započítavajú písmena po pozícii \(k\).
- B = tá, do ktorej sa započítava písmeno na pozícii \(k\).
- C = tá, do ktorej sa započítavajú písmena pred pozíciou \(k\).
Keď odčítame magické hodnoty rôznych kúzel, tak časti C sa vynulujú (lebo boli rovnaké). Časti B boli rôzne, takže ich rozdiel nie je nula, ale zároveň je v absolútnej hodnote menší ako \(47^{k+1}\) (lebo je to najviac \(25\cdot 47^k\)). Časti A sú v oboch kúzlach násobky čísla \(47^{k+1}\) a keď ich odčítame, dostaneme tiež násobok čísla \(47^{k+1}\). Celkový rozdiel teda nemôže byť násobokom čísla \(47^{k+1}\) a preto to nemôže byť nula.
Keďže rozdiel magických čísel rôznych kúzel nemôže byť nula, tak tieto magické čísla nemôžu byť rovnaké.
Ako teda môže Merlin rýchlo zisťovať, či sú dve kúzla vo Veľkom zvitku rovnaké? Pri otázke “Je \(i\)-te a \(j\)-te kúzlo vo veľko zvitku rovnaké?” stačí, aby namiesto pracného porovnávania kúzel porovnal ich magické hodnoty. Tie nájde na \(i\)-tom a \(j\)-tom riadku Malého zvitku. Už totiž vieme, že dve kúzla sú rovnaké vtedy a len vtedy, keď majú rovnaké magické hodnoty.
Fakt, že v Malom zvitku sú hodnoty predpočítané, je dôležitý. Inak by pri každej otázke Merlin počítal magickú hodnotu pre obe kúzla znovu. Musel by tak prejsť všetky znaky oboch kúzel.
Podúloha b.
To, čo chceme robiť, je postupne porovnať súčet hľadanej vzorky so súčtom každého 1000 znakového reťazca v knihe. Otázkou je len, ako efektívne zistiť všetky tieto súčty.
Súšet prvých 1000 čísel zistíme tak, že čísla jednoducho sčítame. Každý ďalší súčet však budeme vedieť zistiť na dve matematické operácie z predošlého súčtu tak, že odčítame prvé číslo a pripočítame jedno ďalšie číslo.
Napísané matematicky (\(T\) je reťazec obsahujúci Pendragonovu knihu, \(T[i]\) je pozícia \(i\)-teho znaku v abecede a \(t_i \dots t_j\) je podreťazec \(T\) obsahujúci znaky od \(i\) po \(j\), vrátane): \[T[i] + T[i+1] + \dots + T[i+999] - T[i] + T[i+1000] = T[i+1] + T[i+2] + \dots + T[i+1000]\] Alebo alternatívne: \[S(t_i \dots t_{i+999}) - T[i] + T[i+1000]) = S(t_{i+1} \dots t_{i+1000})\]
Podúloha c.
To, čo chceme robiť, je postupne porovnať magické číslo vzorky \(R\) s magickým číslom každého súvislého úseku v \(K\). Otázka je len, ako efektívne zistiť magické číslo všetkých týchto úsekov.
Najprv si spočítame mocniny čísla \(47\) od \(1\) až po \(47^r\). Potom spočítame magické číslo \(R\) a prvých \(r\) písmen \(K\).
Každé ďalšie magické číslo dostaneme tak, že predošlé číslo vynásobíme \(47\), odpočítame \(47^r\)-krát hodnota prvého písmena a pripočítame hodnotu ďalšieho písmena v poradí.
Napísané matematicky:
\[47 (47^{r-1}K_i + 47^{r-2}K_{i+1} + \dots + K_{i+r-1}) - 47^r K_i + K_{i+r} = 47^{r-1}K_{i+1} + 47^{r-2}K_{i+2} + \dots + K_{i+r}\] Alebo alternatívne: \[47 \cdot M(k_i \dots k_{i+r-1}) - 47^r K_i + K_{i+r} = M(k_{i+1} \dots k_{i+r})\]
Tu je program, ktorý načíta knihu \(K\) a reťazec \(R\) a vypíše všetky výskyty \(R\) v \(K\).
K, R = input(), input()
k, r = len(K), len(R)
p = 47**r
def c(x):
return ord(x)-ord('a')+1
magic_R, magic_K = 0, 0
for i in range(r):
magic_R = magic_R*47 + c(R[i])
magic_K = magic_K*47 + c(K[i])
for i in range(k-r+1):
if magic_R == magic_K:
print("vyskyt na pozicii", i+1)
if i+r < k:
magic_K = magic_K*47 - c(K[i])*p + c(K[i+r])Všimnite si, že toto riešenie funguje aj ako riešenie podúlohy b.
Podúloha d.
Aby sme sa vyhli pracnému a pomalému porovnávaniu reťazcov znak po znaku, budeme opäť porovnávať len ich magické hodnoty. V tomto prípade teda potrebujeme rýchlo spočítať magické hodnoty každého začiatku a každého konca.
Sme si istí, že po prečítaní riešenia predošlej podúlohy by ste to hravo zvládli spraviť, preto si ukážeme trochu iné riešenie.
Vypočítame si najprv magické hodnoty len pre všetky začiatky reťazca \(T\). Prvý začiatok je len jeden znak a má magickú hodnotu ako hodnota tohto znaku: \[Z(1) = T[0]\]
Všimnite si, že \(Z\) indexujeme od \(1\). Magická hodnota každého ďalšieho začiatku je len hodnota ďalšieho znaku plus 47-krát predošlá magická hodnota: \[Z(i) = T[i-1] + 47\cdot Z(i-1)\]
Rozmyslite si, prečo to tak je. Magické hodnoty koncov dokážeme s konštantným množstvom operácií zistiť čisto z magických hodnôt začiatkov. Označme si dĺžku celého kúzla \(n\). Potom Magická hodnota posledných \(i\) písmen je nasledovná:
\[K(i) = (Z(n) - 47^i \cdot Z(n-i)))\]
Takto by vyzeral program, ktorý načíta kúzlo zo vstupu a vypíše, koľko potrebuje kúzlo many.
S = input()
n = len(S)
def c(x):
return ord(x)-ord('a')+1
Z = [0]
m47 = [1]
for i in range(n):
m47.append(47*m47[-1])
Z.append(c(S[i]) + 47*Z[-1])
mana = 0
for i in range(1, n+1):
if Z[i] == Z[n] - m47[i] * Z[n-i]:
mana += 1
print(mana)Použitie v praxi
Na čo nám je toto celé užitočné a ako sa podobný princíp používa v praxi?
Ak by sme programy napísané vyššie spustili, zistili by sme, že nebežia oveľa rýchlejšie ako programy, ktoré by porovnávali reťazce znak po znaku. Totiž Python, narozdiel od čarodejníkov, nevie porovnávať veľké čísla konštantne rýchlo.
Magické číslo 10000 znakového reťazca bude mať vyše 16000 cifier a porovnať takéto čísla počítaču niečo trvá. Aby sme sa vyhli veľým číslam, budeme namiesto veľkých čísel používať len ich zvyšok po delení nejakým prvočíslom \(P\). Tento zvyšok je menší ako \(P\). Ak teda napríklad zvolíme \(P = 1000000009\), čísla budú mať len 10 a menej cifier.
Pozrite si tieto dva programy:
Ide o prepis riešení z podúloh c a d s tým, že všetky medzivýsledky modulujeme číslom MOD. Číslo \(47\) bolo nahradené všeobecnou premennou POW, lebo čo nám bráni použiť iné číslo, však?
Dôsledky toho, že namiesto magického čísla použijeme zvyšok tohto čísla po delení číslom MOD sú dva:
- Celý program je teraz veľmi rýchly (spraví len toľko operácií ako je dĺžka vstupného reťazca, krát nejaká konštanta).
- Občas vypíšeme zlú odpoveď. Môže sa totiž stať, že dve rôzne magické čísla majú rovnaký zvyšok.
Pri vhodnej voľbe čísel POW a MOD (obe by mali byť prvočísla, hoci to samo o sebe vždy nestačí) bude šanca omylu malá, nebudeme však zachádzať do hlbších detailov, lebo by sme narazili na skutočnú mágiu1.
Algoritmus, ktorý hľadá vzorku v texte pomocou tejto techniky sa volá Rabinov-Karpov algoritmus.
vysokoškolskú algerbu ;)↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.