posloupnosti. loha m jist e en pro ka dou nepr zdnou posloupnost, v krajn m p pad je v sledkem slo 1, pokud dan posloupnost dn del palindrom neobsahuj

INFORMATIKA Maxim ln
palindrom (lohy z MO { kategorie P, 24. st)

;
  PAVEL T PFER Matematicko-fyzik
ln fakulta UK, Praha

Tentokr t se v na
em seri lu zajmavch loh z Matematick olympi dy { kategorie P vr tme hodn daleko do historie. Kategorie P vznikla ve 35. ro nku MO ve
kolnm roce 1985/86 a hned v n sledujcm 36. ro nku (tzn. ve
kolnm roce 1986/1987) byla v dom cm kole zad na n sledujc jednoduch loha s velmi kr tkm zad nm.

???

Kone nou posloupnost sel nazveme symetrickou, jestlie se nezmn, zap
eme-li jej prvky v obr cenm poad. Navrhnte algoritmus, kter pro libovolnou kone nou posloupnost kladnch celch sel ur  dlku jejho nejdel
ho souvislho seku, kter je symetrickou posloupnost. Napklad pro posloupnost 3, 1, 2, 3, 2, 1, 4, 2, 1 je tato dlka 5 (nebo nejdel
m souvislm symetrickm sekem je 1, 2, 3, 2, 1).

???

K zad n je
t doplme, e souvislmu symetrickmu seku njak posloupnosti (napklad posloupnosti znak, tzn. textu) se tak k palindrom. kolem tedy je ur it dlku maxim lnho palindromu v zadan Matematika - fyzika - informatika 19 2009/2010

297

posloupnosti. loha m jist e
en pro kadou nepr zdnou posloupnost, v krajnm ppad je vsledkem slo 1, pokud dan posloupnost  dn del
 palindrom neobsahuje (kad prvek posloupnosti je palindromem dlky 1). Nepoaduje se ur it maxim ln palindrom samotn, nebo ten na rozdl od dlky nemus bt ur en jednozna n, v dan posloupnosti me bt obsaeno vce rznch palindrom te maxim ln dlky. Pi e
en lohy budeme pedpokl dat, e zn me dlku zadan posloupnosti (tzn. po et jejch prvk N ), abychom si celou posloupnost mohli uloit do pole a s tmto polem pak v programu d le pracovat. V dob vzniku kategorie P Matematick olympi dy je
t nebyla zad n soutnch loh formulov na takto precizn, e
itel pouze teoreticky navrhovali algoritmy, ale neprogramovali je. V tehdej
 dob studenti nemli prakticky  dn pstup k po ta m, take ani v olympi d se pochopiteln nee
ily praktick lohy u po ta . Nalzt njak spr vn e
en tto lohy je velmi snadn, jedn se o jednu z vbec nejleh ch loh, kter dosud byly v souti MO { kategorie P zad ny. loha je pesto velmi zajmav , jakmile za neme navren e
en posuzovat z hlediska asov sloitosti algoritm. e
en s kubickou asovou sloitost O(N 3 ) je trivi ln a navrhne ho jist kad bez del
ho pem
len. e
en s kvadratickou asovou sloitost O(N 2 ) ji vyaduje ur it n pad, ale nalzt ho nen obtn. Zato asov optim ln e
en pracujc v line rnm ase O(N ) vymysl jen m lokdo a pro vt
inu ten  asi bude hodn velkm pekvapenm u jenom samotn zji
tn, e je tuto lohu mon v line rnm ase vye
it. Pro po dek za neme od toho nejprimitivnj
ho e
en. Zadanou posloupnost sel si ulome do pole, abychom se k prvkm posloupnosti mohli opakovan vracet. Z posloupnosti pak budeme postupn vybrat v
echny rzn souvisl seky a kad z nich vdy otestujeme, zda je symetrick. Prbn si pitom pamatujeme dlku dosud nejdel
ho nalezenho palindromu. Po otestov n symetrie v
ech sek, kter je mon ze zadan posloupnosti vybrat, budeme jist zn t hledanou dlku maxim lnho palindromu. Popsan e
en d v sice spr vn vsledek, ale je zna n neefektivn. Ozna me-li po et sel ve zpracov van posloupnosti symbolem N , vyaduje tento algoritmus proveden O(N 3 ) operac. Z posloupnosti dlky N lze toti vybrat  dov N 2 rznch souvislch sek, nebo N zpsoby postupn volme levou mez vybranho seku a ke kad zvolen lev mezi v prmru N=2 zpsoby volme pravou mez. K otestov n symetri nosti kadho z nich je pak teba provst O(N ) porovn n. 298

Matematika - fyzika - informatika 19 2009/2010

Popsan algoritmus jsme naprogramovali v Pascalu ve tvaru funkce MaxPalindrom1. Pomocn funkce Palindrom1 slou k testov n, zda je zvolen sek sel v poli A symetrick. function Palindrom1(var A: Pole Odkud, Kam: integer): boolean {test, zda sek pole A mezi indexy Odkud -- Kam je palindrom} var i, j: integer begin i:=Odkud j:=Kam while (i<j) and (A i]=A j]) do begin i:=i+1 j:=j-1 end Palindrom1:= i>=j end {function Palindrom1} function MaxPalindrom1(var A: Pole N: integer): integer var Leva, Prava, MaxDelka: integer begin MaxDelka:=0 for Leva:=1 to N do for Prava:=Leva to N do if Palindrom1(A, Leva, Prava) and (Prava-Leva+1 > MaxDelka) then MaxDelka:=Prava-Leva+1 MaxPalindrom1:=MaxDelka end {function MaxPalindrom1}

Ne pikro me k asymptoticky lep
mu e
en, uk eme si, e ur it rozdly v rychlosti vpo tu mohou bt i mezi rznmi programy s asovou sloitost O(N 3 ) zaloenmi na pr v popsan my
lence systematicky probrat a testovat v
echny souvisl seky. Lep
 organizac pr ce je mon alespo ste n snit po et prov dnch operac a zkr tit tak prmrnou dlku vpo tu. Jestlie jsme u napklad na
li palindrom dlky 5, je zbyte n ztr cet as testov nm symetrie v
ech dal
ch souvislch sek krat
ch ne 6. I kdybychom njak takov krat
 symetrick sek nalezli, na celkov vsledek to stejn nebude mt vliv. Dobrm n padem na zrychlen vpo tu proto je prohlet seky v poad podle jejich dlky, po naje nejdel
m z nich. Dky tomuto uspo d n meme vybr n a tesMatematika - fyzika - informatika 19 2009/2010

299

tov n sek ukon it, jakmile najdeme prvn palindrom. V
echny dal
 by ji byly stejn dlouh nebo krat
 a nemohly by tedy ovlivnit celkov vsledek. U
etme tak pr ci s testov nm v
ech krat
ch sek. Algoritmus m ov
em i nad le asovou sloitost v nejhor
m ppad O(N 3 ), zlep
ili jsme pouze jeho prmrnou asovou sloitost. Zrychlen bude vznamn tehdy, jestlie v posloupnosti existuje njak dlouh palindrom. M -li nejdel
 palindrom v posloupnosti dlku 1, neu
etme oproti pedchozmu e
en tm nic. N sledujc funkce MaxPalindrom2 realizuje popsanou pravu e
en. K testov n symetrie sek vyuv stejnou pomocnou funkci Palindrom1, kterou jsme pouili v pedchozm ppad, take ji zde znovu neuv dme. function MaxPalindrom2(var A: Pole N: integer): integer var Leva, Delka: integer begin for Delka:=N downto 1 do for Leva:=1 to N-Delka+1 do if Palindrom1(A, Leva, Leva+Delka-1) then begin MaxPalindrom2:=Delka exit end end {function MaxPalindrom2}

Zamysleme se nyn nad tm, jakou zmnou algoritmu bychom mohli dos hnout vraznj
ho zrychlen vpo tu. V dosud popsanch algoritmech me existovat cel ada takovch dvojic sel, kter jsou navz jem porovn v na vcekr t. Dje se tak pi zkoum n sek vnoench do sebe. Jestlie budou napklad bhem vpo tu prov dny testy sek v rozmez index h1 10i a h2 9i a pokud se prvn a des t prvek sob rovnaj, potom budou druh a dev t prvek posloupnosti mezi sebou zbyte n porovn v ny opakovan, pi obou uvedench testech. K vylep
en algoritmu bude proto vhodn prov dt najednou testov n symetrie v
ech sek se spole nm stedem. Musme si uvdomit, e palindrom maxim ln dlky me obsahovat bu lich, nebo sud po et sel. Podle toho bu je jeho stedem nkter z prvk zadan posloupnosti, nebo jeho sted le mezi dvma sousednmi prvky. Celkov tedy existuje 2N ; 1 monch umstn stedu palindromu (N prvk, N ; 1 pozic mezi nimi), kter musme v
echny vy
etit. Pro kad z tchto 2N ; 1 mst ur me dlku maxim lnho palindromu se stedem ve zvolenm mst. Nalezen takovho maxim lnho palindromu je 300

Matematika - fyzika - informatika 19 2009/2010

snadn. Postupn od zvolenho stedu smrem k obma okrajm posloupnosti porovn v me dvojice sel stejn vzd lench od stedu. To prov dme tak dlouho, dokud jsou porovn van sla shodn a z rove tak dokud nenarazme na nkter z okraj posloupnosti. Pro kad z uvaovanch sted se vykon maxim ln N=2 porovn n, take celkov se provede nejv
e N 2 porovn n sel. Algoritmus m tedy asovou sloitost O(N 2). Vsledkem vpo tu je maximum z dlek maxim lnch palindrom, kter jsme zskali pro jednotliv uvaovan stedy. Tak tento algoritmus jsme pro v s naprogramovali v Pascalu. Pomocn funkce Palindrom3 tentokr t slou k ur en dlky maxim lnho palindromu se zadanm stedem. Meme ji pout jak pro hled n maxim lnho palindromu lich dlky se stedem v nkterm prvku posloupnosti, tak i pro hled n maxim lnho palindromu sud dlky se stedem mezi dvma sousednmi prvky. To je realizov no pomoc dvojice parametr Stred1, Stred2. V ppad lich dlky bude funkce vol na se stejnou hodnotou obou tchto parametr (oba ur uj index prostednho prvku zkoumanho seku), pi hled n palindromu sud dlky se budou pi vol n funkce hodnoty tchto parametr li
it o 1 (parametry ur uj indexy sousednch prvk posloupnosti, mezi nimi le sted zkoumanho seku). function Palindrom3(var A: Pole N, Stred1, Stred2: integer): integer {dlka maximlnho palindromu se stedem mezi prvky Stred1, Stred2} var i: integer begin i:=0 while (Stred1-i>=1) and (Stred2+i<=N) and (A Stred1-i]= =A Stred2+i]) do i:=i+1 if Stred1=Stred2 then Palindrom3:=2*i-1 else Palindrom3:=2*i end {function Palindrom3} function MaxPalindrom3(var A: Pole N: integer): integer var Stred, Delka, MaxDelka: integer

Matematika - fyzika - informatika 19 2009/2010

301

begin MaxDelka:=1 for Stred:=1 to N do begin Delka:=Palindrom3(A, N, Stred, Stred) {lich dlka} if Delka>MaxDelka then MaxDelka:=Delka Delka:=Palindrom3(A, N, Stred, Stred+1) {sud dlka} if Delka>MaxDelka then MaxDelka:=Delka end MaxPalindrom3:=MaxDelka end {function MaxPalindrom3}

Uveden algoritmus meme je
t d le vylep
ovat, ale zrychlen vpo tu nebude pli
vznamn a z pis algoritmu se stane o dost sloitj
m. Je napklad mon proch zet stedy testovanch sek nikoliv postupn zleva doprava, jako v pedchozm e
en, ale od stedu cel posloupnosti smrem k obma okrajm posloupnosti. Vpo et pak meme ukon it ve chvli, kdy vzd lenost uvaovanho stedu od bli
ho okraje posloupnosti bude men
 ne polovina dlky maxim lnho dosud nalezenho palindromu. V takov situaci je toti jist, e del
 palindrom ji nenajdeme. Tm se me snit po et provedench vol n pomocn funkce Palindrom3, pro !stedy" blzk k okrajm posloupnosti se vol n ji nebude prov dt. Takto upraven algoritmus m ov
em nad le asovou sloitost v nejhor
m ppad O(N 2 ), zlep
ili jsme pouze jeho prmrnou asovou sloitost. Opakuje se podobn situace, jakou jsme ji jednou vidli { zrychleni bude vznamn tehdy, jestlie v posloupnosti existuje njak dlouh palindrom. M -li naopak nejdel
 palindrom v posloupnosti dlku 1, vpo et vbec nezrychlme. N sledujc funkce MaxPalindrom4 vyuv stejnou pomocnou funkci Palindrom3 jako v pedchozm ppad, take ji zde neuv dme podruh. function MaxPalindrom4(var A: Pole N: integer): integer var Stred1, Stred2, Delka, MaxDelka: integer begin Stred1:=N div 2 + N mod 2 {sted posloupnosti} Stred2:=N div 2 + 1 {sted posloupnosti} if N mod 2=0 then {posloupnost sud dlky} MaxDelka:=Palindrom3(A, N, Stred1, Stred2)

302

Matematika - fyzika - informatika 19 2009/2010

else MaxDelka:=1 while Stred1*2-1 > MaxDelka do begin Delka:=Palindrom3(A, N, Stred1, Stred1) if Delka>MaxDelka then MaxDelka:=Delka Delka:=Palindrom3(A, N, Stred2, Stred2) if Delka>MaxDelka then MaxDelka:=Delka Delka:=Palindrom3(A, N, Stred1-1, Stred1) if Delka>MaxDelka then MaxDelka:=Delka Delka:=Palindrom3(A, N, Stred2, Stred2+1) if Delka>MaxDelka then MaxDelka:=Delka Stred1:=Stred1-1 Stred2:=Stred2+1 end MaxPalindrom4:=MaxDelka end {function MaxPalindrom4}

lohu m me sp
n vye
enou, ale tm na
e snaha o nalezen co nejefektivnj
ho e
en nekon . Jak jsme se ji zmnili v vodu, problm ur en dlky maxim lnho palindromu lze kupodivu e
it je
t mnohem lpe, a to v line rnm ase vzhledem k dlce zkouman posloupnosti. K tomuto asov optim lnmu e
en se vr tme v p
tm sle. (Pokraovn) (Autorkou vodn ilustrace je Mgr. Jaroslava ermkov ze Suchch Lazc.)

Palindrom REDAKCE

Vyhled me-li slovo palindrom na internetu, dozvme se mnoho zajmavho. Pedn zjistme, e palindrom je slovo, v ta, slo, obecn jakkoli sekvence symbol , kter m tu vlastnost, e ji lze st v libovoln m sm ru (zprava doleva nebo zleva doprava) a m vdy stejn vznam. Pitom se Matematika - fyzika - informatika 19 2009/2010

303

neuvauj ppadn mezery a interpunk n znamnka, ani se nerozli
uj mal a velk psmena. Palindrom je napklad slovo nezaazen nebo vta Kuna nese nanuk, i kdy pi zptnm pesnm ten dostaneme kunan esen anuK V e
tin tak zanedb v me rky nad samohl skami (i h ek nad e), take vta Kobyla m mal bok. se ad ke zn mm palindromm, i kdy obr cen postup d v kob lam m alyboK. Jinak je to s psmeny s h kem, ty se poaduji spr vn, i kdy teba ve vt Nekouk k u oken to je jedno, protoe  je stedn psmeno. Pi jedn souti  k z kladnch
kol dostali soutc za kol pipravit program, kter u vty vloen z kl vesnice zjist, je-li to palindrom (pracuje se jen s anglickou abecedou a slicemi). Uv dme zde postup t soutcch, jejich programy maj ur it odli
nosti. Form ln sti vodu programu jsme sjednotili. program PalindrA var I: Integer Tex, L, P: string C: Char begin WriteLn('Zjistovani palindromu') Write('Zadej text: ') ReadLn(Tex) L := '' P := '' for I := 1 to Length(Tex) do begin C := Tex I] if C in 'a'..'z'] then C := UpCase(C) if C in 'A'..'Z','0'..'9'] then begin P := P + C L := C + L end end

304

Matematika - fyzika - informatika 19 2009/2010

if L = P then WriteLn('je') else WriteLn('neni') ReadLn end.

Soutc A si de#nuje dva na po tku pr zdn etzce L a P , pak te postupn jednotliv znaky ze zadanho textu a mal psmena pev d na velk . Jestlie na ten a ppadn upraven znak je velk psmeno nebo slice, pid v jej k etzci P zprava a k etzci L zleva. Tm jsou ignorov ny ostatn na ten znaky a dotaz, zda L = P odpovd na ot zku, zda byl zadan text palindrom. Program funguje zcela spr vn, ale z hlediska naprogramov n v nm najdeme ur it ne
ikovnosti. Msto pkaz C := Tex I] if C in 'a'..'z'] then C := UpCase(C)

by bylo lep
 napsat do programu jednoduch pkaz C := UpCase(Tex I])

kterm bychom dos hli pln stejnho efektu. Standardn funkce UpCase toti sama testuje, jak znak dostala ve vstupnm parametru, mal psmena pev d na velk a ostatn znaky vrac beze zmny. Druh ne
ikovnost je skryta ve vytv en znakovho etzce L. Zatmco pkaz P := P + C bude vykon n v konstantnm ase (hodnota znaku C se jednodu
e pid na konec etzce P), pkaz L := C + L m s m o sob line rn asovou sloitost. Cel znakov etzec, kter je obsahem promnn L, se v nm toti mus posunout o jeden znak doprava, aby vzniklo voln msto pro znak C pid van na jeho za tek. Rychlej
 by bylo pevr cen etzec L vbec nevytv et, sestavit pouze etzec P tvoen z ppustnch znak (v
echna psmena jsou v nm ji pevedena velk ) a pak jednodu
e otestovat, zda je etzec P symetrick: I := 1 J := Length(P) while I < J) and (P I] = P J]) do begin Inc(I) Dec(J)

Matematika - fyzika - informatika 19 2009/2010

305

end if I >= J then WriteLn('je') else WriteLn('neni') program PalindrB var I: Integer Tex, L, P: string C: Char begin WriteLn('Zjistovani palindromu') Write('Zadej text: ') ReadLn(Tex) L := '' P := '' for I := 1 to Length(Tex) do if Tex I] in 'A'..'Z','a'..'z'] then begin C := UpCase(Tex I]) L := L + C P := C + P end if L = P then WriteLn('je') else WriteLn('neni') ReadLn end.

Soutc B postupuje v podstat stejn s tm rozdlem, e kad znak testuje jen jednou a pkaz UpCase pak pouije na v
echna psmena (soutc A jen na mal ). Av
ak soutc B zapomnl na slice. program PalindrC var I, J: Integer Tex, Xet: string

306

Matematika - fyzika - informatika 19 2009/2010

begin WriteLn('Zjistovani palindromu') Write('Zadej text: ') ReadLn(Tex) Xet := '' J := 0 for I := 1 to Length(Tex) do if Tex I] in 'A'..'Z','a'..'z'] then begin Tex I-J] := UpCase(Tex I]) Xet := Tex I-J] + Xet end else Inc(J) if Copy(Tex,1,Length(Xet)) = Xet then WriteLn('je') else WriteLn('neni') ReadLn end.

Soutc C si vol dv etzcov promnn Tex a Xet, do Tex je na ten vstupn text. Pak vstupn text upravuje tak, e povolen znaky (psmena) klade od indexu 1 postupn za sebou zpt do promnn Tex (do promnn Xet je pid v zleva), m se na ten vstup pepisuje (tedy ni ). Odpov pak d v ot zka, zda etzec Xet je roven prvn sti (stejnho rozsahu) etzce Tex. Stejn jako B zapomnl i C na slice. e
en soutcho C je na prvn pohled zd nliv sporn v tom, e u
etil jednu promnnou L, do n soutc A a B ukl dali nov vytv en etzec z ppustnch znak. Tato spora v
ak nen vbec podstatn a bylo j dosaeno za cenu ni
 pehlednosti a hor
 srozumitelnosti programu. Takov zpsob programov n v m proto rozhodn nememe doporu it. Soutc B a C mohli bez dal
 zmny svho programu roz
it ppustnou mnoinu o znaky '0' : : : '9', pkaz UpCase slicm nijak neubl. Tak by vyhovli podmnk m soute. Neefektivita spojen s vytv enm pevr cenho etzce je v jejich programech stejn , jako v ppad soutcho A, a
la by tak napravit stejnm zpsobem. Na z vr si uve me je
t dva palindromy, prvn povaujeme za velmi poveden a druh za docela vtipn: A man, a plan, a canal { Panama V elipse sp lev. Matematika - fyzika - informatika 19 2009/2010

307