V textových editoroch zvyčajne máš funkciu na hľadanie v texte. Zadáš tam napríklad “abcd” a potom ti to nájde všetky výskyty “abcd” v texte. Lenže čo ak hľadáš niečo, čo sa nedá popísať tak jednoducho? Napríklad (1) “chcem nájsť všetky slová, ktoré začínajú na a.” Alebo (2) “chcem nájsť všetky také slová, že prvé písmeno je a, potom ľubovoľné jedno písmeno, potom b alebo c a potom hocikoľko ďalších.”

Pre jednoduchosť budeme hľadať v tejto úlohe iba slová, ktoré sa skladajú z malých písmen a až z. Do vyhľadávania si ale pridáme nejaké špeciálne znaky, ktoré budú hľadať niečo iné ako to písmeno.

• Hviezdička (*) znamená “ľubovoľne veľakrát (aj 0) zopakované predošlé písmeno.” Teda napríklad ak dáme hľadať ab*c, tak to znamená: také slová, ktoré začínajú na a, potom je ľubovoľne veľa b-čiek, a nakoniec c. Teda sú to slová ac, abc, abbc, abbbc, a tak ďalej.

• Otáznik (?) znamená “to písmeno predtým tam môže, ale nemusí byť.” Teda napríklad ab?c znamená: najprv a, potom možno b, a nakoniec c. Teda to sú slová ac a abc.

• Zvislá čiara (|) znamená “to predtým alebo to potom”. Teda napríklad ak hľadáme ab|c, tak to je ab alebo c.

• Zátvorky (()) označujú skupinu. Keď dáme hviezdičku za skupinu, tak to znamená, že môže byť hocikoľko krát zopakovaná celá tá skupina, nielen jedno písmeno. Podobne otáznik za skupinou znamená, že celá tá skupina tam môže, ale nemusí byť. Zvislá čiara vo vnútri skupiny znamená, že “alebo” sa týka iba toho vo vnútri. Takže napríklad a(bc)*d znamená a, hocikoľko krát bc a nakoniec d, a a(bc|d)e znamená a, potom bc alebo d, a nakoniec e. Môže byť aj viac skupín vnútri v sebe. Napríklad a(b(cd)?)* znamená a a potom b a možno cd a to zopakované hocikoľko krát. Teda to je napríklad abbcdbcdbbcdb.

• Hranaté zátvorky ([]) označujú skupinu písmen. Dovnútra sa môžu písať len písmená a znamená to, že tam môže byť ľubovoľné jedno z nich. Za skupinu písmen môžeme tiež dať otáznik alebo hviezdičku a týka sa to potom celej skupiny. Teda napríklad a[bc]? znamená a a potom možno b alebo c. Je to to isté ako guľaté zátvorky a v nich medzi každými dvoma písmenami |, ale toto je kratšie a možno prehľadnejšie.

Týmto “vyhľadávacím slovám” sa hovorí regulárne výrazy (alebo tiež regexy, z anglického regular expressions) a používajú sa aj v praxi. Napríklad je dosť možné, že v tvojom textovom editore, v ktorom programuješ, sa dá vyhľadávať aj pomocou nich. V tejto úlohe je ale trochu zjednodušená verzia oproti tomu, čo sa používa inde.

Úloha

Táto úloha je interaktívna, tu je zadanie. Tam si môžeš jednak skúšať napísať nejaký regex a slovo a otestovať, či slovo zodpovedá tomu regexu (teda či by taký regex také slovo našiel).

Okrem toho sú tam aj zadania úlohy. Je niekoľko podúloh, v každej máš napísať regex, ktorý zodpovedá práve nejakej skupine slov. Stránka ti vie aj automaticky otestovať vzor, teda zistiť, či tvoj vzor je naozaj správny. Ako popis nám potom odovzdaj vzory, ktoré si použil(a), netreba k nim písať nič viac.