3. Základ úspechu vzorové riešenie

2 2
aa
ba

2

3 6
bdb
acaabd

11

1 10
a
aaaaaaaaaa

55

Najjednoduchšie riešenie, priamočiaro “hrubou silou” vyzerá nasledovne: Označme si reťazce fembotky a Helboja \(F\) a \(H\). Vyskúšame všetky možné podreťazce \(H\) – postupným výberom začiatkov a koncov. Každý podreťazec po znakoch skontrolujeme, či sa také písmenko nenachádza aj v \(F\) – prejdením celého \(F\). Ak tam bola aspoň jedna spoločná téma-písmenko, podreťazec zarátame. Časová zložitosť tohoto prístupu je \(O(h^3 \cdot f)\) – máme \(h(h+1)/2\) podreťazcov po najviac \(h\) písmen, z ktorých každý skontrolujeme za najviac \(f\) krokov.

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

int main() {
  int f, h;
  string F, H;
  cin >> f >> h;
  cin >> F >> H;
  long long pocet = 0;
  for (int i = 0; i < h; i++) {
    for (int j = i; j < h; j++) {
      for (int k = i; k <= j; k++) {
        bool spolocna = false;
        for (int l = 0; l < f; l++) if (H[k] == F[l]) { spolocna = true; break; }
        if (spolocna) { pocet++; break; }
      }
    }
  }
  cout << pocet << '\n';

  return 0;
}

Všimnime si, že netreba stále prechádzať celý reťazec \(F\) – namiesto toho vieme prejsť \(F\) na začiatku raz, pre každé písmenko si zapamätať, či je v ňom a následne to rýchlo kontrolovať pri prechádzaní. Dostaneme čas \(O(f+h^3)\).

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

string F, H;
bool je_v_F[32]; // tabulka pre pismenka, v globalnych je default vsade 0/false

int main() {
  int f, h;
  cin >> f >> h;
  cin >> F >> H;
  for (int i = 0; i < f; i++) je_v_F[F[i]-'a'] = true;
  long long pocet = 0;
  for (int i = 0; i < h; i++)
    for (int j = i; j < h; j++)
      for (int k = i; k <= j; k++)
        if (je_v_F[H[k]-'a']) { pocet++; break; }
  cout << pocet << '\n';

  return 0;
}

Ďalej sa zamyslime, čo sa stane, keď v \(H\) pre daný začiatok úseku nájdeme koniec taký, že tento úsek už obsahuje spoločnú tému s \(F\). Tento koniec môžeme ľubovoľne posúvať ďalej a stále budeme mať aspoň jednu túto istú spoločnú tému. Ako nám to pomôže? Pre každý možný začiatok nájdeme najbližšie písmenko, ktoré sa vyskytuje aj v \(F\). Ak žiadne nenájdeme, tak zjavne nemáme podreťazec so spoločnou témou nikde ďalej. Nech začiatok je na pozícií \(i\) a najbližšie spoločné písmenko na \(j>=i\). Všetkých podreťazcov začínajúcich v \(i\) obsahujúcich \(j\) je \(h-j\) (ak indexujeme od \(0\) po \(h-1\)). Takže tento príslušný počet zarátame a pohneme sa na ďalší začiatok. Začiatkov je \(h\) a pre každý prejdeme najviac \(h\) písmen, čo nám dáva časovú zložitosť \(O(f+h^2)\).

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

string F, H;
bool je_v_F[32];

int main() {
  int f, h;
  cin >> f >> h;
  cin >> F >> H;
  for (int i = 0; i < f; i++) je_v_F[F[i]-'a'] = true;
  long long pocet = 0;
  for (int i = 0; i < h; i++){
    int prva_spol;
    for (prva_spol = i; prva_spol < h; prva_spol++) {
      if (je_v_F[H[prva_spol]-'a']) break;
    }
    pocet += h-prva_spol;
  }
  cout << pocet << '\n';
  return 0;
}

Nakoniec sa pozrime, čo sa deje pri hýbaní sa na ďalší začiatok úseku. Kde mohla byť predošlá najbližšia spoločná téma? Ak bola hneď na predošlom začiatku, tak je už za nami a musíme nájsť novú. Inak je stále najbližšia tá istá. Budeme mať premennú pre pozíciu najbližšej spoločnej témy a keď sa už začiatok ocitne za ňou, budeme ju zvyšovať, kým nenájdeme dalšiu spoločnú tému alebo koniec. Túto premennú zvýšime celkovo iba \(h\)-krát a každému začiatku vieme povedať, koľko príslušných podreťazcov z neho zarátame. Dostávame rýchle vzorové riešenie v \(O(f+h)\).

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

string F, H;
bool je_v_F[32];

int main() {
  int f, h;
  cin >> f >> h;
  cin >> F >> H;
  for (int i = 0; i < f; i++) je_v_F[F[i]-'a'] = true;
  long long pocet = 0;
  int ns = -1; // najblizsia spolocna tema (pozicia)
  for (int i = 0; i < h; i++){
    if (ns < i) {
      for (ns = i; ns < h; ns++) if (je_v_F[int(H[ns]-'a')]) break;
    }
    pocet += h-ns;
  }
  cout << pocet << '\n';

  return 0;
}

Treba si dať pozor na veľkosť odpovede – môže presiahnuť rozsah 32-bitovej premennej.

Všimnite si, ako sme z jednoduchšieho riešenia zrýchľovali. Vždy vyhodíme niečo, čo zbytočne prechádzame. Takto vieme často nájsť použiteľné riešenia. Pamäťová zložitosť bola vo všetkých prípadoch \(O(f+h)\), nakoľko sme si pamätali iba načítané reťazce a konštantne veľa pomocnej pamäte.