6. Opatera zvieratiek vzorové riešenie

abcdabcd

bab

napisaasipan

napisaasipan

abcdefghijklmnopqrstuvwxyz

f

Našou úlohou je vybrať takú podpostupnosť vstupného reťazca, že tvorí palindróm. Táto podpostupnosť navyše nemusí byť súvislá a dokonca ani najdlhšia možná, stačí ak bude obsahovať \(100\) znakov (poprípade, ak tam nie je takých \(100\) znakov, tak musíme nájsť tú najdlhšiu).

Pokúsme sa zamyslieť nad tým, ako môže vyzerať nejaký najjednoduchší palindróm. Napríklad môže obsahovať len písmená jedného druhu, ako je to v palindrómoch \(aaaa\) alebo \(ddddd\). To ale znamená, že ak náš vstupný reťazec obsahuje \(100\) výskytov toho istého písmena, vieme nájsť riešenie veľmi jednoducho. Proste vyberieme \(100\) takýchto písmen.

Náš program teda môže začať nasledovne: Prejde celým vstupných reťazcom a pre každé písmeno si spočíta počet jeho výskytov. Ak sa niektoré písmeno nachádza v reťazci aspoň \(100\) krát, vypíšeme výsledok skladajúci sa iba z tohoto písmena a program ukončíme.

Pomohli sme si? Veru áno. Aký dlhý môže byť reťazec, v ktorom sa niečo takéto nestane? Každé písmeno sa tam môže vyskytovať najviac \(99\) krát, teda bude mať dĺžku \(99\cdot 26 = 2574\). Keď pridáme ďalší znak, túto vlastnosť pokazíme. Inak povedané¹, ľubovoľný reťazec dĺžky aspoň \(2575\) obsahuje aspoň \(100\) rovnakých znakov. Výrazne sme teda zmenšili obmedzenie na dĺžku vstupu, pre ktorú je naša úloha netriviálna.

Hľadanie najdlhšieho palindrómu

Zostáva nám teda vyriešiť tú zložitejšiu úlohu – ako nájsť najdlhší podpalindróm vo vstupnom reťazci? Takáto úloha je pomerne klasická a preto sa oplatí poznať jej riešenie. Dokonca sa ani nebudeme zaoberať tým, či je ten palindróm dlhý najviac \(100\), lebo už nám to viac pri riešení nepomôže.

Poďme sa vrhnúť rovno na popis riešenia. Nebude to nič iné ako jednoduchá rekurzia s memoizáciou, ktorú si hneď vysvetlíme. To čo hľadáme je najdlhší palindróm od pozície \(0\) po pozíciu \(n\).

Jedna možnosť je, že písmená na pozíciách \(0\) a \(n-1\) sú rôzne. V tom prípade aspoň jedno z týchto písmen nebude vo výsledku. Ak by totiž boli obe, boli by na kraji našej podpostupnosti a tým pádom by sme nemali palindróm. To znamená, že odpoveď bude buď najdlhší palindróm od pozície \(0\) po pozícii \(n-1\) alebo najdlhší palindróm od pozície \(1\) po pozíciu \(n\). A toto sú nejaké menšie podproblémy, ktoré môžeme riešiť rekurzívne.

Druhá možnosť je, že obe písmená na krajných pozíciách sú rovnaké. V tom prípade ich môžeme zobrať do výsledku (ktorý je teraz o jedna dlhší) a hľadáme najdlhší palindróm od pozície \(1\) po pozíciu \(n-1\).

Náš problém sme si teda zapísali ako jednoduchú rekurzívnu funkciu, ktorá bude počítať aký je najdlhší palindróm od pozície \(\ell\) po pozíciu \(r\), a ktorú by sme teraz mali vedieť bez problémov implementovať. Nezabudnite však na to, že ak už vyrátate odpoveď pre nejakú dvojicu \((\ell,r)\), treba si túto odpoveď zapamätať, aby sme ju nemuseli pri ďalšom opýtaní opäť rátať celú. Na zapamätanie nám poslúži jednoduché dvojrozmerné pole. Bez tohto zapamätávania (memoizácie) by bola časová zložitosť riešenia exponenciálna.

Takisto nemôžete zabudnúť na to, že na konci musíme vypísať reťazec a teda musíme vedieť spätne zistiť, ktoré písmená patria do najdlhšieho palindrómu. Toto si môžete buď pamätať v ďalšom dvojrozmernom poli, kde si poznačíte, ktorým spôsobom dostanete najdlhší palindróm z daného úseku alebo si to budete značiť priamo pri simulácii. Dajte si však pozor, že keď bude najdlhší palindróm dlhší ako \(100\) znakov, musíte ho na túto dĺžku skrátiť.

Na záver sa už len pozrime na časovú a pamäťovú zložitosť. Každý stav rekurzie vieme vyrátať v konštantnom čase, stačí keď sa pozrieme na tri iné čísla. Stavov je ale \(n^2\), takže časová zložitosť nášho riešenia je \(O(n^2)\). A rovnako to bude aj s pamäťovou zložitosťou, lebo si musím zapamätať výsledok pre každý možný stav.

Keď máme nejako popísať časovú zložitosť celého riešenia, označme si \(d\) maximálnu dĺžku palindrómu a \(a\) počet písmen abecedy. Dĺžka vstupu je \(n\). Potom časová zložitosť je \(O(n + (\min(n,d \cdot a))^2)\). Keď považujeme \(d\) a \(a\) za konštanty, tak je to jednoducho \(O(n)\).

#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#define For(i,N) for(int i=0; i<N; i++)
#define Fors(i,s) for(int i=0; s[i]; i++)
using namespace std;

vector<int> P(26,0);
char buf[2000000];
vector<vector<int> > T(3000, vector<int>(3000,-1));

int maxd( int l, int r){
    if(l > r) return 0;
    if( T[l][r] != -1 ) return T[l][r];
    if( buf[l] == buf[r] ) return T[l][r] =1+ (l!=r) + maxd( l+1, r-1 );
    return T[l][r] = max( maxd(l+1, r), maxd(l, r-1) );
}

int main(){
    scanf(" %s", buf);
    Fors(i, buf) P[buf[i]-'a']++;
    For(i,26) if(P[i] >= 100){
        For(j,100) printf("%c", 'a'+i);
        printf("\n");
        return 0;
    }
    
    int i=0, j=strlen(buf)-1;
    int maxi = maxd(i,j);
    string zac="", kon="";
    while(i<=j){
        while(i<=j && maxd(i,j) == maxi ) i++;
        if(i-1<=j && maxd(i,j) != maxi) zac += buf[i-1];
        while(j >= i && buf[j] != buf[i-1] ) j--;
        if(j > i-1) kon.push_back( buf[j] ); j--;
        maxi = maxd(i,j);
    }
    reverse(kon.begin(), kon.end() );
    if(zac.length()+kon.length()>100) {
        zac="";
        For(i,50) zac+=kon[i];
        For(i,50) zac+=kon[49-i];
    }
    else zac += kon;
    printf("%s\n", zac.c_str());
    return 0;
}