Palindrom2

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.

Spre exemplu, 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ă. De aici, problema se rezumă la a determina această lungime maximă a unui palindrom care se termină pe ultima poziţie a şirului. Se fixează un indice k succesiv pe poziţiile 1, 2, ..., n şi se verifică dacă şirul S[k..n] este un palindrom:

Algoritm Pali(k, n, S, ok):
  i = k
  j = n
  ok = adevărat
  cât timp i < j şi ok execută
    dacă S[i] != S[j] atunci
      ok = fals
    sfârşit dacă
    i = i + 1
    j = j - 1
  sfârşit cât timp
Sfârşit algoritm.

Dacă ok este adevărat, atunci S[k..n] este palindrom. Algoritmul se opreşte la primul palindrom determinat, acesta fiind de lungimea cea mai mare.
Complexitate: O(n2).