2. Iregulérna Strava vzorové riešenie

4
anna
ABBA
anna
ABB
lopta
HOKEJ
banany
ANANAS

ano
nie
ano
nie

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;
	}
}