Algo palindrome

[Pablitos23]

Dato un intero n stampa tutte le stringhe palindrome 2n. E' corretto? Avrei bisogno di una mano per Motivare la complessità dell'algoritmo pari a O(n*2^n). Grazie in anticipo e buona giornata.

Pal(n:int, h:prefix, S:array)
   if h==2n then
      if ( isSafe(S) ) then
           stampa S
  else
      for x in {a,b} do
         S[h+1] = x
         Pal(n,h+1,S)

isSafe(S:array, n:int)
   i = 1
   f = 2n
   while i <= f do
      if S[f] == S[i] then
          i++
          f--
      else
         return FALSE
  return TRUE

[vict85]

Usi sempre lo stesso approccio e spesso non è quello migliore. Cosa significa palindroma? Significa che S = S[2n-i] ovvero che sostanzialmente la prima metà della stringa definisce in maniera deterministica la seconda. Siccome non ci sono altre condizioni, il tuo problema si trasforma in generare ogni stringa di lunghezza uguale a n e stamparla due volte (la seconda invertendo l'ordine). Insomma, di fatto devi modificare semplicemente la funzione stampa per stampare la versione palindroma della stringa che riceva in input e lanciare questa funzione da una funzione che genera tutte le stringhe di lunghezza n.

[Pablitos23]

Grazie mille per la risposta, quindi in questo modo?

Pal(n:lunghezza, h:prefix, S:array)
   
   if h == n then
        stampa(S)

  else
       for x in {a,b} do
           S[h+1] = a
           if(isSafe(S)) Pal(n,h+1,S)

stampa(S)
   for i=1 to n
        output S[i]
   for i=n downto 1
        output S[i]

Dove isSafe è come la precedente.

Per la complessità, il costro di visita di una foglia è pari a O(n), dove n è la lunghezza delle stringhe generate.
Quindi un upper bound sarà $O( n * 2^n )$ dove $2^n$ sono tutte le possibili stringhe generate sull'alfabeto {a,b} di lunghezza n.