4. Substringy vzorové riešenie

5
prask

3 12

15
aekeocjekolskrj

66 54

Teória

Aby sme vedeli spočítať skóre súrodencov, potrebujeme spôsob, ako určiť, či je písmeno samohláska, alebo spoluhláska. Bohužiaľ túto vlastnosť písmen počítač nedokáže rozpoznať sám od seba a musíme mu najskôr povedať ako taká samohláska vyzerá. Aby sme si to zjednodušili zapamätáme si len ako vyzerajú samohlásky a necháme program rozhodnúť či kontrolované písmeno je alebo nie je samohláska. Kontrola prebehne tak, že program prehľadá pole samohlások a pri zhode s kontrolovaným písmenom okamžite rozhodne, že písmeno je samohláska, inak po dokončení prehľadávania rozhodne, že písmeno je spoluhláska (pretože to nebola žiadna zo samohlások). Takýmto spôsobom program nemusí vôbec vedieť o tom, ako vyzerajú spoluhlásky a stále dostaneme správne riešenie. Ak by sme pri riešení implementovali aj separátne pole pre spoluhlásky, tak by program v pomalších jazykoch nezbehol na plný počet bodov.

Riešenie hrubou silou

Najpriamočiarejšie riešenie je skontrolovať, akým písmenom sa začína každý možný substring v slove pomocou spôsobu, ktorý sme si vysvetlili v teórii. Všetkých substringov je rádovo \(n^2/2\), lebo pre písmeno na indexe \(i\) existuje \(n-i\) substringov, ktoré ním začínajú a \(i\) substringov, ktoré sa ním končia. Takéto riešenie má časovú zložitosť \(O(n^2)\) a v časovom limite vyrieši len prvé \(2\) sady.

Za takéto riešenie bolo možné získať \(40\) bodov.

n = int(input())
a = input()
s = [0, 0]

# zname samohlasky
sam = ["a", "e", "i", "o", "u", "y", "A", "E", "I", "O", "U", "Y"]

# spocitame zaciatky spol. a sam. vsetkych substringov v slove
for i in range(n):
    for j in range(n):
        if a[i:j+1].startswith(a[i]):
            if sam.__contains__(a[i]):
                s[0] += 1
            else:
                s[1] += 1
print(*s)

Vzorové riešenie

Ak chceme zlepšiť časovú zložitosť, musíme znížiť počet krokov, ktoré program vykoná. Môžeme si všimnúť, že počet substringov začínajúcich písmenom na pozícii \(i\) je \(n - i\). Od začiatku substringu \(n_i\), ktorý poznáme, sa substring vie predlžovať len do jedného smeru a to len presne \(n - i\) krát, lebo tam slovo končí a substring sa už nemá ako predĺžiť. Počet predĺžení od písmena vieme pre každé písmeno v slove zistiť v konštantnom čase, takže celú úlohu vieme vyriešiť v lineárnom čase \(O(n)\). Pamäťová zložitosť je \(O(1)\), lebo si v pamäti držíme len konštantný počet samohlások a výsledky.

Keby sme si počet samohlások označili \(s\), časová zložitosť by bola \(O(ns)\). Keby sme si tieto samohlásky pamätali vo vhodnej štruktúre, vedeli by sme o každom písmene zistiť, či je to samohláska v konštantom čase. Takouto štruktúrou je napríklad unordered_set v C++, alebo set v pythone. Toto vylepšenie však na plný počet bodov nebolo potrebné.

#include <iostream>
using namespace std;

int main()
{
    int n;
    string a;
    cin >> n;
    cin >> a;
    long long out[] = {0,0};

    // zname samohlasky
    string sam = "aeiouyAEIOUY";

    // pre kazde pismeno pripocitam pocet substringov
    for(int i=0; i<n; i++) {

        // je pismeno samohlaska?
        bool result = false;
        for(int j=0; j<sam.size(); j++) {
            if (a[i] == sam[j]) result = true;
        }
        
        if (result) {
            out[0] += n - i;
        } else {
            out[1] += n - i;
        }
    }

    cout << out[0] << " " << out[1] << endl;
    return 0;
}

n = int(input())
a = input()
s = [0, 0]

# zname samohlasky
sam = ["a", "e", "i", "o", "u", "y", "A", "E", "I", "O", "U", "Y"]

# pre kazde pismeno pripocitam pocet substringov
for i in range(n):
    if sam.__contains__(a[i]):
        s[0] += n - i
    else:
        s[1] += n - i
print(*s)