4. Iné jazýčky vzorové riešenie

3
AAB
baa

3

6
AHOJKY
mnauky

56

8
AHOJACAU
mnaumnau

54

Našim cieľom je spočítať súčet dĺžok všetkých preložiteľných intervalov. Najjednoduchší spôsob, ako to spraviť, je postupne všetky takéto intervaly nájsť.

Pomalé prehľadávanie podreťazcov

Všetky preložiteľné intervaly môžeme nájsť napríklad tak, že sa pozrieme na všetky možné intervaly, a pre každý zistíme, či sa dá preložiť alebo nie.

Každý interval je jednoznačne definovaný svojim začiatkom a koncom, takže na prejdenie všetkých nám stačia dva for cykly – jeden pre začiatok a druhý pre koniec (pričom si dáme pozor, aby koniec nikdy nebol pred začiatkom). Každý interval potom prejdeme tretím cyklom, v ktorom otestujeme, či sa dá preložiť.

To vieme spraviť veľmi jednoducho. Vyrobíme si dve polia dĺžky anglickej abecedy (malé a veľké písmená) a pre každý znak, ktorý by sa mohol vyskytnúť vo vrchnom alebo spodnom reťazci si budeme pamätať, na aký znak v opačnom reťazci sa prekladá. Na začiatku testovania intervalu budú všetky hodnoty samozrejme prázdne (špeciálne označené, že zatiaľ žiadny preklad nemáme).

Keď potom interval prechádzame, dostávame postupne dvojice znakov, ktoré sa pokúšame do poľa zapísať. Ak je pre nejaké písmeno v poli už zapísaný jeho preklad, a tento preklad nie je rovnaký, ako by sme chceli doplniť, znamená to, že aktuálny interval je nepreložiteľný a možeme jeho testovanie ukončiť. Ak sa nám podarí úspešne dokončiť testovanie intervalu, pridáme jeho dĺžku (rozdiel konca a začiatku plus jedna) k odpovedi.

Tento prístup má časovú zložitosť \(O(n^3)\) – prechádzame každý z kvadraticky mnoho intervalov dĺžky až \(n\). Pamäťová zložitosť je lineárna, keďže si musíme pamätať celé pôvodné pole, aby sme ho mohli prechádzať opakovane.

Zafixovanie začiatku

Zrejme je ale jasné, že pri predošlom prístupe počítame mnohokrát to isté. Napríklad pokiaľ by bol interval \([1, 10]\) preložiteľný, samostatne by sme počítali všetkých 10 intervalov dĺžky jedna (\([1, 1], [2, 2], ... [10, 10]\)), potom samostatne všetkých 9 intervalov dĺžky 2 (\([1, 2], [2, 3], ... [9, 1]\)), až po jeden interval dĺžky 10 (\([1, 10]\)).

Ak by sme vedeli využiť, že interval \([1, 10]\) je preložiteľný a zároveň maximálny (teda jeho predĺženie doprava už preložiteľné nie je), mohli by sme si ušetriť veľa práce tým, že ho nájdeme iba raz a dĺžky všetkých intervalov v ňom spočítame naraz. Tu by však mohol nastať problém – pokiaľ by bol preložiteľný aj interval \([2, 11]\) (avšak \([1, 11]\) nie), mohlo by sa sťať, že započítame množstvo kratších intervalov viackrát.

Skúsme si teda zakaždým zafixovať začiatok intervalu, nájsť koniec maximálneho intervalu, ktorý sa ešte dá preložiť, a pripočítať k výsledku len dĺžky takých jeho podintervalov, ktoré začínajú na našom zafixovanom začiatku. Napríklad pre začiatok na pozícii \(1\) a maximálny preložiteľný interval \([1, 10]\) zarátame intervaly \([1, 1], [1, 2], ... [1, 10]\) s dĺžkami \(1 + 2 + ... + 10 = 55\), teda dokopy \((d + 1) \times (d + 2) / 2\), kde \(d\) je rozdiel začiatku a konca.

Takto určite zarátame každý preložiteľný interval práve raz, takže dostaneme správnu odpoveď. Časová zložitosť je \(O(n^2)\), pre každý začiatok intervalu musíme nájsť jeho koniec, ktorý môže byť až \(n\) znakov vzdialený.

Optimálne okienkovanie

Stále počítame niektoré veci zbytočne. Napríklad pokiaľ by sme si pri počítaní maximálneho intervalu pre začiatok na pozícii \(1\) poznačili dvojicu A – a, rovnakú dvojicu by sme našli na pozícii \(5\) a na pozícii \(11\) by sme oproti písmenu A našli b, vieme, že pre začiatky na pozíciach \(2\), \(3\), \(4\) a \(5\) by sme tiež našli rovnaké konce intervalov na pozícii \(11\). Tieto intervaly by sme teda vôbec nemuseli počítať.

Rozviňme túto myšlienku do vzorového riešenia: budeme si udržovať dva indexy – začiatok a koniec intervalu – a okrem prekladov si pre každé písmeno budeme pamätať aj počet výskytov dáneho prekladu, ktoré v aktuálnom intervale máme.

Vždy budeme najskôr dopredu posúvať koniec intervalu, dokým bude celý interval preložiteľný. Keď už to nepôjde, pretože nájdeme pre niektoré písmeno iný preklad (čo sa môže stať aj pre obe písmená na danej pozícii naraz), než máme aktuálne uložený, budeme interval skracovať od začiatku, až dokým sa nezbavíme všetkých prekladov pre dané písmeno. Práve preto, aby sme vedeli, dokedy máme interval skracovať, si potrebujeme pre každý preklad udržovať aj počet jeho výskytov.

Pripočítavať výsledky budeme vždy pri predlžovaní intervalu – pri každom predĺžení započítame všetky intervaly, ktoré končia na aktuálne pridanom mieste. Ich počet budeme počítať rovnako, ako pri počítaní intervalov s fixným začiatkom. Určite započítame všetky intervaly, pretože oproti predošlému prístupu sme zmenili iba smer, ktorým ich započítavame (nič nemení, či ich počítame podľa koncov alebo podľa začiatkov).

Zmení sa tiež časová zložitosť – keďže začiatok aj koniec posunieme dokopy najviac \(n\)-krát a pre každý posun spravíme konštantné množstvo operácii, bude aj celková časová zložitosť lineárna. Pamäťová zložitosť zostane lineárna – stále si musíme pamätať, v najhoršom prípade, celé pôvodné pole. Veľkosť anglickej abecedy je konštantná, a teda aj pamäť potrebná na uloženie aktuálnych prekladov.

#!/usr/bin/env python 3

def main():
    N = int(input())
    L = input()
    M = input()

    translation_L = dict() # slovnik: znak --> (prelozeny znak, pocet vyskytov)
    translation_M = dict()
    begin, end = 0, 0
    ans = 0 # vysledok

    while end < N:        
        end += 1 # skusime posunut koniec
        l = L[end - 1]
        m = M[end - 1]

        while ((l in translation_L.keys() and translation_L[l][0] != m) or
               (m in translation_M.keys() and translation_M[m][0] != l)):
                # ak musime najskor skracovat zo zaciatku
            begin += 1
            remove_L = L[begin - 1]
            translation_L[remove_L] = (translation_L[remove_L][0],
                                       translation_L[remove_L][1] - 1)
            if translation_L[remove_L][1] == 0:
                del translation_L[remove_L] # odoberame vyskyt zo slovnika
            
            remove_M = M[begin - 1]
            translation_M[remove_M] = (translation_M[remove_M][0],
                                       translation_M[remove_M][1] - 1)
            if translation_M[remove_M][1] == 0:
                del translation_M[remove_M] # odoberame vyskyt zo slovnika
        
        # uz mozeme posunut koniec

        # pridame novy preklad alebo zvysime pocet jeho vyskytov
        if not l in translation_L.keys(): translation_L[l] = (m, 0)
        translation_L[l] = (translation_L[l][0],
                            translation_L[l][1] + 1)

        # pridame novy preklad alebo zvysime pocet jeho vyskytov
        if not m in translation_M.keys(): translation_M[m] = (l, 0)
        translation_M[m] = (translation_M[m][0],
                            translation_M[m][1] + 1)

        # zapocitame intervaly konciace na novej end pozicii
        ans += (end - begin) * (end - begin + 1) // 2
    
    print(ans)

main()        

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    string L, M; cin >> L >> M;

    unsigned long long ans = 0; // vysledok
    vector<pair<char, int>> translations_L(128), translations_M(128); // pismeno, pocet vyskytov
    // 128 je malo, nemusime teda komplikovane pocitat indexy pismen v abecede
    unsigned long long begin = 0, end = 0;

    while (end < N){
        ++end; // skusime posunut koniec
        char l = L[end - 1];
        char m = M[end - 1];

        while ((translations_L[l].second != 0 && translations_L[l].first != m) ||
               (translations_M[m].second != 0 && translations_M[m].first != l)){
                // ak musime najskor skracovat zo zaciatku
            begin += 1;
            
            char remove_L = L[begin - 1];
            --translations_L[remove_L].second; // odoberame vyskyt zo slovnika

            char remove_M = M[begin - 1];
            --translations_M[remove_M].second; // odoberame vyskyt zo slovnika
        }

        // uz mozeme posunut koniec

        translations_L[l].first = m;
        ++translations_L[l].second; // pridame novy vyskyt
        
        translations_M[m].first = l;
        ++translations_M[m].second; // pridame novy vyskyt

        // zapocitame intervaly konciace na novej end pozicii
        ans += ((end - begin) * (end - begin + 1) / 2);
    }

    cout << ans << endl;
}