5. Obmedzená slovná zásoba vzorové riešenie

aha
haha

9

zeleny
akokrava

48

stastnynovyrok
vyrok

64

Táto úloha bola zaujímavá tým, že na jej vyriešenie nebolo potrebné poznať žiadne dátové štruktúry, ani techniky riešenia úloh ako napríklad dynamické programovanie. Ba dokonca, ak ste v úlohe hľadali nejaké tie štandardné štruktúry a algoritmy, tak ste pravdepodobne zabili veľa času :)

Prvý krok k úspešnému vyriešeniu je rozobrať si niekoľko malých prípadov ručne, a snáď pritom odpozorovať niečo o tom, ako sa to celé správa.

Na začiatok si všimneme, že ak niektoré slovo na vstupe je prázdne, tak odpoveď je zrejme \(0\). (Nemá prefix ani sufix dĺžky aspoň 1.) V ďalšom texte predpokladáme, že obe slová majú dĺžku aspoň \(1\).

Hrubá sila

Každé slovo vieme nájsť tak, že zoberieme nejaký prefix \(A\), nejaký sufix \(B\) a spojíme ich. Naskytá sa nám tak nasledujúce riešenie:

Vyskúšame všetky možné prefixy \(A\). Pre každú možnosť vyskúšame všetky sufixy \(B\). Spojíme ich do jedného slova, a uložíme do vreca. Po odskúšaní všetkých možností z vreca odstránime všetky duplikáty. Počet zvyšných prvkov vo vreci je hľadaný výsledok.

Jediný problém môžeme mať pri vyhadzovaní duplikátov – ako to spraviť? Zamyslime sa, ako by sme odstránili duplikáty z postupnosti čísel – postupnosť utriedime, a následne vieme, že rovnaké prvky sú v postupnosti hneď za sebou. Prejdeme teda postupnosť od začiatku po koniec, a každý prvok, ktorý je rôzny od predchádzajúceho, hodíme do výsledného vreca (ktoré už neobsahuje duplikáty).

To isté spravíme so slovami. Slová budeme porovnávať lexikograficky (takým spôsobom sú slová usporiadané napríklad v slovníkoch). To znamená, že sa najprv pozrieme na prvý znak. Ak sa slová na ňom nezhodujú, za lexikograficky menšie prehlásime to, ktorého znak je v abecede skôr. Ak sa slová na ňom zhodujú, pokračujeme ďalším písmenom.

Čo sa ale stane, ak niektoré slovo už nemá nasledujúci znak? Jednoducho ho prehlásime za menšie. Teda ak je jedno zo slov prefixom druhého, tak je od neho lexikograficky menšie.

Napríklad \(jablko < jablkoahruska\), \(a < bcdef\), prázdny reťazec je menší od ľubovoľného slova, …

Čo sa týka implementácie, väčšina programovacích jazykov štandardne vie porovnávať dva reťazce, a tiež väčšinou majú štandardnú funkciu na triedenie. Stačí ju teda zavolať na naše pole všetkých kombinácii prefixov a sufixov.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main () {
  string A, B;
  cin >> A >> B;
  int sa = A.size(), sb = B.size();

  vector<string> vrece;
  
  for (int i=1; i<=sa; i++)
    for (int j=1; j<=sb; j++)
      vrece.push_back(A.substr(0, i) + B.substr(sb-j, j));
   
  sort(vrece.begin(), vrece.end());
  
  int res = 0;
  for (int i=0; i < vrece.size(); i++) {
    if (i==0)
      res++;
    else if (vrece[i] != vrece[i-1])
      res++;
  }
  cout << res << "\n";
  return 0;
}

Časová zložitosť tohto riešenia je \(O(n^3 \log{n})\), a pamäťová \(O(n^3)\), kde \(n\) je veľkosť vstupu. (Máme \(O(n^2)\) reťazcov, a každý má dĺžku \(O(n)\). Triedenie spraví \(O(n^2 \log{n^2})\) porovnaní, každé v čase \(O(n)\), takže celková zložitosť je \(O(n^2 \log{n^2} \cdot n) = O(n^3 \log{n})\).) V špeciálnych prípadoch je to aj menej (napríklad keď \(|A| = 0\)), ale v najhoršom prípade je to toľkoto.

Jemnejšia sila

Na “odstránenie” duplikátov sa dá použiť aj iný postup – zabezpečíme, že ich nikdy do nášho “vreca” nevložíme.

Na začiatku budeme mať prázdny slovník a postupne vyskúšame pridať všetky kombinácie prefixov \(A\) a sufixov \(B\), tak, ako v predchádzajúcom riešení. Ak práve skúšaná kombinácia ešte nie je v slovníku, pridáme ju doň a zvýšime si počítadlo počtu slov v slovníku o \(+1\). V opačnom prípade ju zahodíme.

Slovník môžeme implementovať ako písmenkový strom (po anglicky trie) alebo ako hashovaciu tabuľku (unordered_map v štandartnej knižnici C++). Vkladanie prvkov a zisťovanie, či už sa tu takýto prvok nachádza trvá týmto štruktúram lineárny čas od dĺžky reťazca.

Oproti predchádzajúcemu riešeniu sme si vylepšili čas o \(\log{n}\) – časová zložitosť je \(O(n^3)\), a pamäťová je rovnaká.

Riešenie postupnými zmenami

Najprv si všimneme, že má zmysel hľadať duplikáty iba v slovách rovnakej dĺžky, nakoľko slová rôznych dĺžok určite nie sú rovnaké. Vieme tak znížiť pamäťovú zložitosť na \(O(n^2)\) – namiesto toho, aby sme si spravili zoznam všetkých kombinácii naraz, stačí nám spraviť si osobitný zoznam pre každú dĺžku. Ten môžeme po spracovaní (vyhodení duplikátov) zahodiť, a tak si nikdy nepamätáme viac ako \(O(n)\) reťazcov dĺžky \(O(n)\) naraz.

Pozrime sa teraz, ako vyzerajú kombinácie s jednou konkrétnou dĺžkou, keď ich spracúvame “sprava doľava” (tak, že začneme kombináciou s najdlhším prefixom \(A\), a postupne zmenšujeme prefix \(A\) a zväčšujeme sufix \(B\)). Napríklad ak máme kombinácie slov \(jablko, hruska\) dĺžky \(8\), tak ich budeme spracúvať v tomto poradí: \[jablkoka, jablkska, jabluska, jabruska, jahruska\]

Zameriame sa na zmeny. Čo sa zmení, keď sa posuniem v zozname o \(1\) ďalej? Posledný znak prefixu sa nahradí znakom sufixu. (Napríklad v treťom posune sme mali prefix \(jabl\) a sufix \(uska\). Posledný znak prefixu, \(l\), sme nahradili znakom sufixu, ktorý v \(hruska\) predchádza \(uska\), teda \(r\).) Ak sú tieto znaky rovnaké, dostaneme to isté slovo – našli sme duplikát. Čo ale ak sú tieto znaky rôzne? Nemôže sa stať, že by sme dostali slovo, ktoré bolo spracované ešte skôr?

Všimnime si ale, že zmeny sa postupne dejú na skorších pozíciách. Prvý posun \(jablkoka \rightarrow jablkska\) nám zmenil znak na pozícii \(6\), druhý posun ovplyvňuje znak na pozícii \(5\), … Teda každá pozícia sa zmení v najviac jednom posune. Ak sa znak na pozícii \(k\) zmenil v nejakom posune z \(\alpha\) na \(\beta\), potom všetky kombinácie pred tým posunom majú na danej pozícii \(\alpha\), a všetky kombinácie po tom posune majú na tej pozícii \(\beta\). Napríklad v presune \(jabluska \rightarrow jabruska\) sa zmenila pozícia \(4\): \[jab\mathbf{l}koka, jab\mathbf{l}kska, jab\mathbf{l}uska \rightarrow jab\mathbf{r}uska, jah\mathbf{r}uska\]

To ale znamená, že ak je nahradený znak rôzny od pôvodného, tak výsledné slovo určite nebolo spracované skôr, lebo všetky slová spracované skôr majú na tejto pozícii pôvodný znak. Našli sme tak novú kombináciu.

Vyskúšame teda všetky možné dĺžky kombinácií, a pre každú spracujeme kombinácie s tou dĺžkou. Pritom nemusíme kombinácie vytvárať (nemusíme materializovať stringy), ale pri spracovaní sa pozeráme iba na \(2\) znaky – pôvodný (pred posunom), a nový (po posune). Časová zložitosť je preto \(O(n^2)\), a pamäťová \(O(n)\).

#include <iostream>
#include <string>
using namespace std;

int main () {
  string A,B;
  cin >> A >> B;

  long long res = (long long) A.size() * B.size();
  int maxdlzka = A.size() + B.size();
  for (int dlzka=2; dlzka<=maxdlzka; dlzka++) {
    int a = A.size();
    int b = dlzka - a;
    while (b<=0) {            // dlzka sufixu B predsa nemoze byt zaporna!!!
      a--;
      b++;
    }
    while (a > 1 && b < B.size()) {
      // prefix tvoria znaky A[0], A[1], ..., A[a-1]
      char povodny = A[a - 1];

      // sufix tvoria znaky B[B.size()-1], B[B.size()-2], ..., B[B.size()-b]
      // a teda znak predchadzajuci tomu sufixu je B[B.size()-b-1]
      char novy = B[B.size() - b - 1];

      if (povodny == novy)    // objavili sme duplikat
        res--;
      a--;
      b++;
    }
  }
  cout << res << "\n";
  return 0;
}

Možno ste si všimli detail v implementácii: Všetkých kombinácií je \(|A| \cdot |B|\) a odčítavame počet duplikátov. Tento detail sa nám bude hodiť za chvíľku.

Počítanie toho istého iným spôsobom

Čo vlastne predchádzajúce riešenie robí? Pozerá sa na niektoré dvojice [pozícia v \(A\), pozícia v \(B\)], a ak sú znaky na týchto pozíciách rovnaké, odráta od výsledku \(1\). Zamyslime sa nad tým, koľkokrát pozrie ktoré dvojice. Zvolíme si nejakú konkrétnu dvojicu \([a,b]\) a chceme zistiť, koľko posunov spôsobí nahradenie znaku na pozícii \(a\) znakom, ktorý je v \(B\) na pozícii \(b\)?

Každá pozícia v \(A\) nám jednoznačne určí, aký má byť prefix pred posunom, a aký je po posune. (Napríklad pozícia \(2\) v \(jablko\) vraví, že pred posunom je prefix \(ja\), a po posune je \(j\).) Pozíciu \(1\) ale neberieme do úvahy, lebo po posune bude prefix prázdny. Zaujímajú nás len kombinácie tvaru [neprázdny prefix \(A\)] zreťazený s [neprázdny sufix \(B\)].

Taktiež každá pozícia v \(B\) nám jednoznačne určí, aký má byť sufix pred a po posune. Nerátame pozíciu \(|B|\). Dostávame tak, že na každú dvojicu \([a,b]\), kde \(a > 1, b < |B|\) sa pozrieme práve raz. Čo to ale znamená? Zvoľme si nejakú pevnú pozíciu \(a\), a povedzme, že na nej je znak \(\alpha\). Potom odrátame \(1\) za každý znak v [\(B\) okrem posledného znaku], ktorý je rovný \(\alpha\). Celkovo si odrátame \(k\), kde \(k\) je počet znakov \(\alpha\) v [\(B\) bez posledného znaku]. Ak máme v [\(A\) bez prvého znaku] \(l\) znakov \(\alpha\), od výsledku dokopy odrátame \(l \cdot k\).

Dopracovali sme sa tak k nasledujúcemu riešeniu: spočítame si počty jednotlivých znakov v [\(A\) bez prvého znaku], [\(B\) bez posledného znaku]. Zo získaných počtov ľahko vypočítame výsledok. Časová zložitosť je \(O(n + \sigma)\), kde \(\sigma\) je veľkosť abecedy.

#include <iostream>
#include <string>
using namespace std;

int main () {
  string A,B;
  cin >> A >> B;
  
  long long pocA[26], pocB[26];
  for (int i=0; i<26; i++) {
    pocA[i]=0;
    pocB[i]=0;
  }
  
  for (int i=1; i<(int)A.size(); i++)
    pocA[A[i]-'a']++;
  for (int i=0; i<(int)B.size()-1; i++)
    pocB[B[i]-'a']++;
  
  long long res= (long long)A.size()*(long long)B.size();
  for (int i=0; i<26; i++)
    res-= pocA[i]*pocB[i];

  cout << res << "\n";
  return 0;
}

Pamäťová zložitosť riešenia je \(O(n + \sigma)\), ale vedeli by sme ju zlepšiť aj na \(O(\sigma)\), ak by sme vstup načítavali po znakoch.