Zadanie

Janko sa na internáte delí o chladničku s ďalšími troma ľuďmi. Často sa mu stáva, že jedlo, ktoré si do nej odloží, mu odtiaľ záhadným spôsobom zmizne. Napríklad, v minulú nedeľu si z domu doniesol lahodné grilované kuracie stehno s ryžou a nivovou omáčkou. Odložil ho na svoju poličku v chladničke s tým, že ho zje v pondelok večer.

V pondelok večer o 19.00 sa po celom dni na fakulte, hladný ako vlk, vrátil na internát. Otvoril chladničku a čo tu vidí? Nič! Stehno a jeho predstavy o lahodnej večeri sú preč.

Povedal si, že to už takto ďalej nemôže pokračovať, a prišiel s nápadom: Uloží si do chladničky okrem jedlých vecí aj veci nejedlé. Všetky veci zabalí do alobalu tak, aby spolubývajúci nevedeli, čo je dnu.

Problém je, že takto ani on nebude vedieť, čo môže bezpečne zjesť. Našťastie, Janko sa nedávno v škole učil o šifrách a tak pozná spôsob, ako si označí balíčky tak, aby ich obsah poznal iba on.

Vytvoril si teda tabuľku, v ktorej každému malému písmenu anglickej abecedy priradil práve jedno veľké písmeno anglickej abecedy. Balíčky si označil dvoma slovami. Prvé sa skladá z malých písmen anglickej abecedy a druhé z veľkých písmen anglickej abecedy. Ak je v balíku jedlo, tak druhé slovo je vytvorené z prvého podľa tejto tabuľky.

Jankoví spolubývajúci, ktorí nepoznajú túto šifru, si tak dosť pravdepodobne pochutia na nejedlých balíčkoch, ktoré môžu obsahovať napríklad drevo alebo kapsuly s pracím práškom.

Napíšte Jankovi program, ktorý mu pomôže zistiť, či je daný balíček jedlý.

Úloha

Na vstupe je zoznam balíčkov v chladničke. Na každom z nich sa nachádzajú práve dve slová. Zistite podľa slov na každom balíčku, či je v ňom jedlo. V balíčku sa nachádza jedlo práve vtedy, keď platí:

  • Každému písmenu v prvom slove je pridelené práve jedno veľké písmeno (obraz) v druhom slove.
  • Rovnaké písmená majú rovnaký obraz.
  • Rozdielne písmená majú rozdielny obraz.
  • Poradie obrazov v druhom slove zodpovedá poradiu písmen v prvom slove.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(1 \leq t \leq 10^4\), počet balíčkov v chladničke. Nasleduje \(t\) popisov balíčkov – dva riadky obsahujúce slová na jednotlivom balíčku. Prvé slovo je tvorené malými, a druhé veľkými písmenami anglickej abecedy. Každé slovo obsahuje aspoň jeden znak. Platí, že súčet dĺžok všetkých slov nepresahuje \(4\,000\,000\).

Formát výstupu

Pre každý balíček na výstup vypíšte “ano”, ak je v ňom jedlo, inak vypíšte “nie”.

Príklady

Input:

4
anna
ABBA
anna
ABB
lopta
HOKEJ
banany
ANANAS

Output:

ano
nie
ano
nie

Zo slova “anna” sa ‘a’ zobrazilo do ‘A’ a ‘n’ do ‘B’

Slovo “ABB” je kratšie než “anna”, takže neplatí, že každé písmeno z prvého slova sa práve raz zobrazí do druhého.

V slove “lopta” sa žiadne písmeno neopakuje, takže päť písmen sa zobrazilo do piatich rôznych obrazov.

Slovo “banany” sa nezobrazilo správne do slova “ANANAS”, keďže až dvom písmenám ‘b’ a ‘n’ je priradené ‘A’.

Zadanie úlohy hovorí, že na vstupe máme dva reťazce a našou úlohou je zistiť, či spĺňajú zadané podmienky. Podmienky vieme zhrnúť tak, že každým rovnakým (malým) znakom prvého slova majú zodpovedať rovnaké (veľké) znaky – obrazy – v druhom slove. Odlišné znaky prvého slova majú mať odlišné obrazy v druhom.

Funkčné riešenie

V najjednoduchšom riešení stačí, ak prejdeme cez všetky dvojice znakov pôvodného slova a overíme, či sú splnené podmienky zo zadania.

V prvom rade skontrolujeme, či sú slová rovnakej dĺžky. Ak nie sú, vieme, že nejaký znak prvého slova nemá žiaden obraz v druhom slove, alebo naopak, a tak vieme hneď povedať, že odpoveď je “nie”.

Teraz prichádza na rad hlavná časť riešenia. Povedzme, že oba reťazce \(A\) a \(B\) dĺžky \(n\) máme načítané v pamäti a prechádzame obe slová po znakoch. Cieľom je overiť, či všetky znaky spĺňajú určené podmienky zo zadania. Pre každú \(i\)-tu dvojicu znakov \(A_i\) a \(B_i\) prechádzame ďalších \(n - i\) dvojíc \(A_j\), \(B_j\). Pri tomto prechádzaní môžu nastať 4 situácie:

  • \(A_j\), \(B_j\) sa zhodujú s \(A_i\), \(B_i\) – vtedy je všetko v poriadku. \(A_i = A_j\) a preto sú rovnaké aj ich obrazy \(B_i = B_j\).

  • \(A_i \neq A_j\) a \(B_i \neq B_j\) – vtedy je tiež všetko v poriadku. Pôvodné písmená sú rozdielne a tak aj ich obrazy sú rozdielne.

  • \(A_i = A_j\) a \(B_i \neq B_j\) (alebo opačne \(A_i \neq A_j\) a \(B_i = B_j\)) znamená, že, buď máme dve rovnaké písmena v pôvodnom slove, ktoré majú odlišné obrazy, alebo, v druhom prípade, sú to rôzne písmena v pôvodnom slove a majú rovnaké obrazy. Oba tieto prípady znamenajú, že sme našli znak, ktorý nespĺňa podmienku zo zadania a odpoveď je tým pádom “nie”.

Ak týmto spôsobom prejdeme celé slovo a nenájdeme žiadnu chybu, podmienky sú splnené pre všetky znaky a teda odpoveď je “áno”.

Časová zložitosť tohto riešenia je \(O(n^2)\), keďže pre každú z \(n\) pozícií \(i\) musíme ešte prejsť rádovo \(n\) pozícií \(j\).

Pamäťová zložitosť je \(O(n)\), lebo si pamätáme dve slová s \(n\) písmenami.

Na vstupe ale možeme dostať slovo dĺžky až \(2\,000\,000\), čo znamená, že pri vyššie spomenutej časovej zložitosti by riešenie bežalo pomerne dlho…

Substitučná šifra

Podmienky zo zadania vieme ale zjednodušiť a preformulovať tak, že chceme, aby sa každé písmeno malej abecedy (z prvého slova) zašifrovalo na písmeno veľkej abecedy (z druhého slova). Tiež musí platiť, že žiadne dve malé písmená sa nemôžu zašifrovať na to isté veľké.

Uvedomme si, že takéto šifrovanie sa dá celé definovať pomocou šifrovacej abecedy, čo je reťazec, v ktorom sa na \(i\)-tom mieste nachádza šifrovaný znak (obraz) \(i\)-teho písmena klasickej abecedy. Napríklad, použitím šifrovacej abecedy ANCDEFGHIJKLMBOPQRSTUVWXYZ vznikne zo slova “abba” slovo “ANNA”. Písmeno a sa pri tom mení na A, b na N.

Takéto šifrovanie sa bežne nazýva substitučná šifra. Našou úlohou je teda zistiť, či šifrovaný text mohol vzniknúť z pôvodného pomocou takejto šifry.

Lepšie riešenie

A práve pomocou šifrovacej abecedy vieme navrhnúť rýchlejšie riešenie! Ak si budeme pamätať šifrovaciu abecedu, tak nemusíme pre každý znak prechádzať celý zvyšok slova, ale stačí nám len overiť, či sú všetky nové znaky zašifrované podľa tej istej abecedy ako predošlé znaky.

Budeme si pamätať dve šifrovacie abecedy, vďaka ktorým budeme vedieť realizovať šifrovanie a dešifrovanie. Jedna abeceda bude šifrovať znaky z pôvodného slova do šifry, a druhá bude inverzná k nej – ak sa podľa šifrovacej abecedy mení a na B, tak podľa dešifrovacej abecedy sa mení B na a.

Pre každý \(i\)-ty znak z pôvodného slova zistíme, či už máme k nemu priradený nejaký obraz v abecede pre šifrovanie. Ak tam žiaden obraz nie je, znamená to, že takéto písmeno sme objavili prvýkrát. V takomto prípade znaku pridelíme obraz podľa jeho šifry, čiže \(i\)-ty znak v druhom slove.

To isté zisťujeme aj pre znaky v druhom, šifrovanom, slove, a vytvárame si dešifrovaciu abecedu.

Ak už \(i\)-ty znak má v šifrovacej abecede priradený obraz, overíme, či sa tento obraz zhoduje s \(i\)-tym znakom v druhom slove. Ak sa nezhodujú, našli sme chybu v šifrovaní – dva rovnaké znaky sú zašifrované na odlišné obrazy. Tiež musíme overiť, či sa už náhodou nejaký odlišný znak nezašifruje na obraz \(i\)-teho. To overíme pomocou doteraz vybudovanej dešifrovacej abecedy.

Pamäťová zložitosť je v podstate rovnaká ako predtým, aj keď si teraz musíme pamätať aj dve abecedy – \(2\times 26\) znakov. To znamená \(O(2\times n + 2\times 26)\), no konštanty môžeme pri odhade zložitostí zanedbať, keďže nás zaujíma iba rádový odhad množstva použitej pamäte. Tým pádom vieme určiť výslednú pamäťovú zložitosť na \(O(n)\).

Pri časovej zložitosti získaváme výrazné zlepšenie a dostávame sa na lineárnu zložitosť, keďže pre každé písmeno vykonáme iba konštantný počet operácií. Takže \(O(n)\).

#include <iostream>
#include <string>

using namespace std;

const int NEDEFINOVANE = 0;

int main() {
	int t;
	cin >> t;

	for (int tt = 0; tt < t; tt++) {
		// v poliach si pamatame, ktore znaky sa sifruju na ktore
		char sifrovy_predpis[26] = {NEDEFINOVANE}, spatny_predpis[26] = {NEDEFINOVANE};

		string text, sifrovany_text;
		cin >> text;
		cin >> sifrovany_text;
		
		if (text.size() != sifrovany_text.size()) {
			cout << "nie" << endl;
			continue;	// slova maju rozdielne dlzky, ideme na dlasiu dvojicu
		}

		bool korektna_sifra = true;
		for (int i = 0; i < text.size(); i++) {
			// prvy vyskyt znaku v povodnom slove, ulozime si prislusny obraz
			if (sifrovy_predpis[ text[i] - 'a' ] == NEDEFINOVANE)
				sifrovy_predpis[ text[i] - 'a' ] = sifrovany_text[i];
			
			// prvy vyskyt sifroveho znaku v sifre, k sifrovemu znaku si ulozime povodny
			if (spatny_predpis[ sifrovany_text[i] - 'A' ] == NEDEFINOVANE)
				spatny_predpis[ sifrovany_text[i] - 'A' ] = text[i];
			
			// ak i-ty znaku textu nie je zasifrovany podla "sifroveho predpisu"
			// alebo i-ty znak sifroveho textu nie je obrazom znaku textu, sifra nie je korektna
			if (sifrovy_predpis[ text[i] - 'a' ] != sifrovany_text[i] || spatny_predpis[ sifrovany_text[i] - 'A' ] != text[i]) {
				korektna_sifra = false;
				break;
			}
		}
		
		if (korektna_sifra)
			cout << "ano" << endl;
		else
			cout << "nie" << endl;
	}
}

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ť.