Ako si tak Červená Čiapočka kráčala lesom, začalo sa pomaly stmievať. Po chvíli slnko úplne zapadlo a Červená Čiapočka už takmer nič nevidela. Ako si tak kráčala temným lesom, zrazu uvidela slabé svetielko. Ihneď sa za ním rozbehla, až kým nedošla k potôčiku. Ako sa tak pozerala, uvidela, že v potôčiku plávajú svietiace vodné hady. Veľmi ju zaujímalo, akú dĺžku má najdlhší had v potôčiku. Pomôž jej to zistiť!
Na vstupe dostaneš postupnosť rôznych znakov. Tvojím cieľom je zistiť, akú dĺžku
má najdlhší had v potôčiku. Had sa skladá z hlavičky ~O dĺžky 1 (jazyk
nepočítame), tela pozostávajúceho zo znakov =, pričom každý znak má dĺžku 1
(pozor, had môže mať aj telo dĺžky 0), a chvostíka > dlžky 1. Všetky hady sú
otočené rovnakým smerom, a to takým, že vľavo sa nachádza hlavička a vpravo
chvostík.
Vstup je jeden riadok, ktorý sa skladá iba zo znakov ~O=>..
Vypíš jeden riadok a ňom dĺžku najdlhšieho hada. Ak sa na vstupe žiadne hady nenachádzajú, vypíš $0$.
~O==>~O>
4
V tomto prípade sú v potôčiku $2$ hady, prvý má dĺžku $4$ a druhý $2$. Najdlhší z nich má teda dĺžku $4$.
~O===.>
0
V tomto prípade v potôčiku nevidíme žiadne hady, takže najdlhší z nich má dĺžku $0$.
Na začiatok si musíme uvedomiť, že had pozostáva z hlavičky ~O, tela tvoreného
znakom = a chvostíka >. Teda medzi hlavičkou a chvostíkom sa musia nachádzať iba
znaky =, inak to nie je had. Taktiež vieme, že všetky hady sú orientované
rovnakým smerom, a to takým, že hlavička je vždy naľavo od chvostíka.
Teda nám stačí prejsť reťazec z ľava do prava, a vždy, keď nájdeme hlavičku hada, pamätať si, že sme v tele hada a počítať jeho dĺžku, až kým nenarazíme na chvostík alebo iný znak. Vytvoríme si premennú, v ktorej uchovávame dĺžku najdlhšieho hada a nastavíme jej hodnotu na $0$. Ak nájdeme chvostík, stačí nám porovnať, či súčasný had je dlhší ako hodnota premennej najdlhší had, ak áno, zmeníme hodnotu premennej na dĺžku tohto hada, ak nie, prechádzame reťazcom ďalej. Taktiež ak nájdeme iný znak, pokračujeme v hľadaní hlavičky.
Časová zložitosť je $O(n)$, lebo prechádzame celým reťazcom iba raz.
Pamäťová zložitosť je $O(1)$, lebo si program pamätá iba niekoľko premenných - súčet dĺžok hadov a premennú, ktorá kontroluje, či sa práve nachádzame v hadovi alebo nie. Vzorový python kód má pamäťovú zložitosť $O(n)$, pretože načítava celý rad do pamäte, čo stačí na vyriešenie úlohy. Ak by sme ale čítali vstup iba po jednotlivých znakoch zo súboru, tak by nám stačilo iba konštantne veľa pamäte.
hadik = input()
najdlhsi_had = 0
telo = 0
som_v_tele = False
for i in range(1,len(hadik)):
if hadik[i-1] == "~" and hadik[i] == "O":
telo = 2
som_v_tele = True
elif som_v_tele and hadik[i]=="=":
telo+=1
elif som_v_tele and hadik[i]==">":
if najdlhsi_had >= telo:
telo = 0
else:
najdlhsi_had = telo
telo = 0
som_v_tele = False
else:
telo = -1
som_v_tele = False
print(najdlhsi_had)