Palindrom
Se aplică metoda Greedy. Conform cerinţei din enunţ se impune să inserăm caractere doar la sfârşitul şirului. Observăm că un palindrom de lungime minimă se obţine prin inserarea unui număr minim de caractere la sfârşitul şirului. Pentru a obţine acest număr minim trebuie să găsim lungimea maximă a unui palindrom care se termină pe ultima poziţie a şirului. Dacă şirul iniţial este abcdzyxyz, palindromul căutat este zyxyz, iar rezultatul va fi abcdzyxyzdcba, adică vom adăuga caracterele aflate în faţa palindromului cu care se termină şirul iniţial, dar în ordine inversă.
Notăm cu T şirul S inversat. Dacă parcurgem şirul S de la stânga la dreapta, va trebui ca pentru fiecare poziţie i să determinăm cel mai lung sufix al şirului S[1..i] care este prefix al şirului T[1..n], unde n este lungimea şirului. Dacă lungimea acestui subşir este lung atunci:
- dacă lung = n – i, atunci am obţinut un palindrom de lungime 2 * lung cu centrul între poziţiile i şi i + 1.
- dacă lung = n – i + 1, atunci am obţinut un palindrom de lungime 2 * lung – 1 cu centrul în poziţia i.
- dacă lung < n – i, atunci nu avem un palindrom şi ignorăm această poziţie.
Pentru a determina acest subşir observăm că este nevoie să construim funcţia prefix (cunoscut din algoritmul KMP de potrivire a şirurilor) pentru şirul T şi să parcurgem ulterior şirul S pentru a determina lungimile.
Algoritmul are complexitatea O(n).
O alta soluţie care ar fi obţinut 100 de puncte este folosirea hashurilor pentru a căuta cel mai lung sufix palindrom (vezi potrivirea şirurilor pe baza algoritmului Rabin-Karp ).
Parcugând şirul de la sfarşit se reţine intr-un hash sufixul obţinut până la acel moment, iar in alt hash inversul acestui sufix. În caz că aceste 2 hashuri sunt identice se reţine poziţia curentă şi se continuă căutarea.
Soluţia se obţine adăugând in ordine inversa, la coada şirului iniţial, caracterele aflate in stanga poziţiei de început a celui mai lung sufix palindrom.
Deoarece compararea celor doua hashuri se face in O(1) algoritmul final va avea complexitatea O(n)
