Python: busca los palíndromos más largos dentro de una palabra y los palíndromos dentro de una palabra / cadena

Así que aquí hay un código que he escrito para encontrar palíndromos dentro de una palabra (para verificar si hay palíndromos dentro de una palabra, incluida la palabra misma) Condición: los espacios entre los caracteres se cuentan y no se ignoran Ejemplo: A, pero tuba es un palíndromo pero técnicamente es debido a los espacios involucrados ahora no lo es. así que ese es el criterio.

Basado en lo anterior, el siguiente código generalmente debería funcionar. Puede probar por su cuenta con diferentes pruebas para ver si este código da algún error.

def pal(text): """ param text: given string or test return: returns index of longest palindrome and a list of detected palindromes stored in temp """ lst = {} index = (0, 0) length = len(text) if length <= 1: return index word = text.lower() # Trying to make the whole string lower case temp = str() for x, y in enumerate(word): # Try to enumerate over the word t = x for i in xrange(x): if i != t+1: string = word[i:t+1] if string == string[::-1]: temp = text[i:t+1] index = (i, t+1) lst[temp] = index tat = lst.keys() longest = max(tat, key=len) #print longest return lst[longest], temp 

Y aquí hay una versión difunta de ella. Lo que quiero decir es que he intentado comenzar desde el medio y detectar palíndromos iterando desde el principio y verificando cada uno de los índices superior e inferior en busca de caracteres verificando si son caracteres iguales. si lo son, entonces estoy comprobando si es un palíndromo como un cheque palíndromo regular. esto es lo que he hecho

 def pal(t): text = t.lower() lst = {} ptr = '' index = (0, 0) #mid = len(text)/2 #print mid dec = 0 inc = 0 for mid, c in enumerate(text): dec = mid - 1 inc = mid + 1 while dec != 0 and inc != text.index(text[-1]): print 'dec {}, inc {},'.format(dec, inc) print 'text[dec:inc+1] {}'.format(text[dec:inc+1]) if dec text.index(text[-1]): inc = text.index(text[-1]) while text[dec] != text[inc]: flo = findlet(text[inc], text[:dec]) fhi = findlet(text[dec], text[inc:]) if len(flo) != 0 and len(fhi) != 0 and text[flo[-1]] == text[fhi[0]]: dec = flo[-1] inc = fhi[0] print ' break if' break elif len(flo) != 0 and text[flo[-1]] == text[inc]: dec = flo[-1] print ' break 1st elif' break elif len(fhi) != 0 and text[fhi[0]] == text[inc]: inc = fhi[0] print ' break 2nd elif' break else: dec -= 1 inc += 1 print ' break else' break s = text[dec:inc+1] print ' s {} '.format(s) if s == s[::-1]: index = (dec, inc+1) lst[s] = index if dec > 0: dec -= 1 if inc < text.index(text[-1]): inc += 1 if len(lst) != 0: val = lst.keys() longest = max(val, key = len) return lst[longest], longest, val else: return index 

diversión de findlet ():

 def findlet(alpha, string): f = [i for i,j in enumerate(string) if j == alpha] return f 

A veces funciona:

     pal('madem') dec -1, inc 1, text[dec:inc+1] sm dec 1, inc 3, text[dec:inc+1] ade break 1st elif sm dec 2, inc 4, text[dec:inc+1] dem break 1st elif sm dec 3, inc 5, text[dec:inc+1] em break 1st elif sm Out[6]: ((0, 1), 'm', ['m']) pal('Avid diva.') dec -1, inc 1, text[dec:inc+1] break 2nd if s avid div dec 1, inc 3, text[dec:inc+1] vid break else s avid dec 2, inc 4, text[dec:inc+1] id break else s vid d dec 3, inc 5, text[dec:inc+1] dd sdd dec 2, inc 6, text[dec:inc+1] id di s id di dec 1, inc 7, text[dec:inc+1] vid div s vid div dec 4, inc 6, text[dec:inc+1] di break 1st elif s id di dec 1, inc 7, text[dec:inc+1] vid div s vid div dec 5, inc 7, text[dec:inc+1] div break 1st elif s vid div dec 6, inc 8, text[dec:inc+1] iva break 1st elif s avid diva dec 8, inc 10, text[dec:inc+1] a. break else s va. dec 6, inc 10, text[dec:inc+1] iva. break else s diva. dec 4, inc 10, text[dec:inc+1] diva. break else sd diva. dec 2, inc 10, text[dec:inc+1] id diva. break else s vid diva. Out[9]: ((0, 9), 'avid diva', ['avid diva', 'd d', 'id di', 'vid div']) 

    Y en base a los Criterios / Condiciones que he puesto:

     pal('A car, a man, a maraca.') dec -1, inc 1, text[dec:inc+1] break else s dec -1, inc 3, text[dec:inc+1] sa ca dec 1, inc 3, text[dec:inc+1] ca break if sa ca dec 2, inc 4, text[dec:inc+1] car break else s car, dec 3, inc 5, text[dec:inc+1] ar, break else s car, dec 1, inc 7, text[dec:inc+1] car, a break 1st elif sa car, a dec 4, inc 6, text[dec:inc+1] r, break 1st elif s car, dec 5, inc 7, text[dec:inc+1] , a break 1st elif s ar, a dec 2, inc 8, text[dec:inc+1] car, a break 1st elif s car, a dec 6, inc 8, text[dec:inc+1] asa dec 5, inc 9, text[dec:inc+1] , am break else sr, a ma dec 3, inc 11, text[dec:inc+1] ar, a man break else s car, a man, dec 1, inc 13, text[dec:inc+1] car, a man, s car, a man, dec 7, inc 9, text[dec:inc+1] am break else sa ma dec 5, inc 11, text[dec:inc+1] , a man break else sr, a man, dec 3, inc 13, text[dec:inc+1] ar, a man, break if s dec 8, inc 10, text[dec:inc+1] ma break if s dec 6, inc 4, text[dec:inc+1] break 1st elif sr dec 3, inc 5, text[dec:inc+1] ar, break else s car, dec 1, inc 7, text[dec:inc+1] car, a break 1st elif sa car, a dec 9, inc 11, text[dec:inc+1] man break else s man, dec 7, inc 13, text[dec:inc+1] a man, break if s dec 5, inc 2, text[dec:inc+1] break 1st elif sc dec 1, inc 3, text[dec:inc+1] ca break if sa ca dec 10, inc 12, text[dec:inc+1] an, break 1st elif s , a man, dec 4, inc 13, text[dec:inc+1] r, a man, break 1st elif s car, a man, dec 11, inc 13, text[dec:inc+1] n, break 1st elif s man, dec 7, inc 14, text[dec:inc+1] a man, a sa man, a dec 6, inc 15, text[dec:inc+1] a man, asa man, a dec 5, inc 16, text[dec:inc+1] , a man, am break else sr, a man, a ma dec 3, inc 18, text[dec:inc+1] ar, a man, a mar break else s car, a man, a mara dec 1, inc 20, text[dec:inc+1] car, a man, a marac break else sa car, a man, a maraca dec 12, inc 14, text[dec:inc+1] , a break 1st elif s an, a dec 9, inc 15, text[dec:inc+1] man, a break if s dec 7, inc 2, text[dec:inc+1] break 1st elif sc dec 1, inc 3, text[dec:inc+1] ca break if sa ca dec 13, inc 15, text[dec:inc+1] asa dec 12, inc 16, text[dec:inc+1] , am break 1st elif s man, am dec 8, inc 17, text[dec:inc+1] man, a ma break 1st elif sa man, a ma dec 6, inc 18, text[dec:inc+1] a man, a mar break 1st elif sr, a man, a mar dec 3, inc 19, text[dec:inc+1] ar, a man, a mara s ar, a man, a mara dec 2, inc 20, text[dec:inc+1] car, a man, a marac s car, a man, a marac dec 1, inc 21, text[dec:inc+1] car, a man, a maraca break 1st elif sa car, a man, a maraca dec 14, inc 16, text[dec:inc+1] am break 1st elif s man, am dec 8, inc 17, text[dec:inc+1] man, a ma break 1st elif sa man, a ma dec 6, inc 18, text[dec:inc+1] a man, a mar break 1st elif sr, a man, a mar dec 3, inc 19, text[dec:inc+1] ar, a man, a mara s ar, a man, a mara dec 2, inc 20, text[dec:inc+1] car, a man, a marac s car, a man, a marac dec 1, inc 21, text[dec:inc+1] car, a man, a maraca break 1st elif sa car, a man, a maraca dec 15, inc 17, text[dec:inc+1] ma break 1st elif sa ma dec 13, inc 18, text[dec:inc+1] a mar break 1st elif sr, a man, a mar dec 3, inc 19, text[dec:inc+1] ar, a man, a mara s ar, a man, a mara dec 2, inc 20, text[dec:inc+1] car, a man, a marac s car, a man, a marac dec 1, inc 21, text[dec:inc+1] car, a man, a maraca break 1st elif sa car, a man, a maraca dec 16, inc 18, text[dec:inc+1] mar break 1st elif sr, a man, a mar dec 3, inc 19, text[dec:inc+1] ar, a man, a mara s ar, a man, a mara dec 2, inc 20, text[dec:inc+1] car, a man, a marac s car, a man, a marac dec 1, inc 21, text[dec:inc+1] car, a man, a maraca break 1st elif sa car, a man, a maraca dec 17, inc 19, text[dec:inc+1] ara s ara dec 16, inc 20, text[dec:inc+1] marac break 1st elif s car, a man, a marac dec 1, inc 21, text[dec:inc+1] car, a man, a maraca break 1st elif sa car, a man, a maraca dec 18, inc 20, text[dec:inc+1] rac break 1st elif s car, a man, a marac dec 1, inc 21, text[dec:inc+1] car, a man, a maraca break 1st elif sa car, a man, a maraca dec 19, inc 21, text[dec:inc+1] aca s aca dec 21, inc 23, text[dec:inc+1] a. break else s ca. dec 19, inc 23, text[dec:inc+1] aca. break else s raca. dec 17, inc 23, text[dec:inc+1] araca. break else s maraca. dec 15, inc 23, text[dec:inc+1] maraca. break else sa maraca. dec 13, inc 23, text[dec:inc+1] a maraca. break else s , a maraca. dec 11, inc 23, text[dec:inc+1] n, a maraca. break else s an, a maraca. dec 9, inc 23, text[dec:inc+1] man, a maraca. break else s man, a maraca. dec 7, inc 23, text[dec:inc+1] a man, a maraca. break else sa man, a maraca. dec 5, inc 23, text[dec:inc+1] , a man, a maraca. break else sr, a man, a maraca. dec 3, inc 23, text[dec:inc+1] ar, a man, a maraca. break else s car, a man, a maraca. dec 1, inc 23, text[dec:inc+1] car, a man, a maraca. break else sa car, a man, a maraca. Out[8]: ((13, 16), ' a ', ['', ' a ', 'c', ' ', 'aca', 'ara', 'r']) 

    A veces, no funciona en absoluto:

      pal('madam') dec -1, inc 1, text[dec:inc+1] sm dec 1, inc 3, text[dec:inc+1] ada break 1st elif sm dec 2, inc 4, text[dec:inc+1] dam break 1st elif sm dec 3, inc 5, text[dec:inc+1] am break 1st elif sm Out[5]: ((0, 1), 'm', ['m']) 

    Ahora, considerando que la señora es un palíndromo muy agradable, debería funcionar y hay muchos casos en los que no me he probado para descubrir qué otros palíndromos legítimos no detecta.

    Q1: ¿Por qué a veces no se detecta?

    P2: Me gustaría optimizar mi segundo código para esa materia. ¿Alguna entrada?

    P3: ¿Qué mejor enfoque hay para un código mucho más eficiente que mi primer código que se repite muchas veces?

    Tu solución me parece un poco complicada. Solo mire todas las subcadenas posibles y revíselas individualmente:

     def palindromes(text): text = text.lower() results = [] for i in range(len(text)): for j in range(0, i): chunk = text[j:i + 1] if chunk == chunk[::-1]: results.append(chunk) return text.index(max(results, key=len)), results 

    text.index() solo encontrará la primera aparición del palíndromo más largo, por lo que si desea la última, sustitúyala por text.rindex() .

    A continuación hay un código que escribí para la misma pregunta. Puede que no esté realmente optimizado, pero funciona como un encanto. Bastante fácil de entender también para principiantes.

     def longestPalindrome(s): pal = [] longestpalin = s l = list(s) if len(s)>0: if len(s)==2: p = l if p[0]==p[1]: return s else: return l[0] else: for i in range(0,len(l)): for j in range(i+1,len(l)+1): p = l[i:j] if p == p[::-1]: if len(p)>len(pal): pal = p p = ''.join(p) longestpalin = p return longestpalin else: return longestpalin 

    La siguiente función devuelve el palíndromo más largo contenido en una cadena dada. Es un poco diferente, ya que utiliza los itertools como se sugiere en esta respuesta . Hay valor en abstraer la generación de combinación. Su complejidad en el tiempo es evidentemente aún cúbica. Se puede adaptar de forma trivial según sea necesario para devolver el índice y / o la lista de palíndromos.

     import itertools def longest_palindrome(s): lp, lp_len = '', 0 for start, stop in itertools.combinations(range(len(s)+1), 2): ss = s[start:stop] # substring if (len(ss) > lp_len) and (ss == ss[::-1]): lp, lp_len = ss, len(ss) return lp 
     a = "xabbaabba" # Provide any string count=[] for j in range(len(a)): for i in range(j,len(a)): if a[j:i+1] == a[i:j-1:-1]: count.append(i+1-j) print("Maximum size of Palindrome within String is :", max(count)) 

    Si te gusta la solución recursiva, he escrito una versión recursiva. También es intuitivo.

     def palindrome(s): if len(s) <= 1: return s elif s[0] != s[-1]: beginning_palindrome = palindrome(s[:-1]) ending_palindrome = palindrome(s[1:]) if len(beginning_palindrome) >= len(ending_palindrome): return beginning_palindrome else: return ending_palindrome else: middle_palindrome = palindrome(s[1:-1]) if len(middle_palindrome) == len(s[1:-1]): return s[0] + middle_palindrome + s[-1] else: return middle_palindrome 

    Aquí hay un código que puede usar para encontrar la subcadena palindrómica más larga:

     string = "sensmamstsihbalabhismadamsihbala" string_shortener = "" pres = 0 succ = 3 p_temp=0 s_temp=0 longest = "" for i in range(len(string)-2): string_shortener = string[pres:succ] if(string_shortener==string_shortener[::-1]): p_temp = pres s_temp = succ for u in range(1000): p_temp-=1 s_temp +=1 string_shortener = string[p_temp:s_temp] if(string_shortener == string_shortener[::-1]): if len(string_shortener)>len(longest): longest = string_shortener else: break pres+=1 succ+=1 print(longest) 
     inputStr = "madammmdd" outStr = "" uniqStr = "".join(set(inputStr)) flag = False for key in uniqStr: val = inputStr.count(key) if val % 2 !=0: if not flag: outStr = outStr[:len(outStr)/2]+key+outStr[len(outStr)/2:] flag=True val-=1 outStr=key*(val/2)+outStr+key*(val/2) print outStr 

    He hecho el nombre de la función como maxpalindrome (s) en este único argumento de cadena ‘s’. Esta función devolverá la subcadena de palíndromo más larga posible y la longitud de la subcadena …

     def maxpalindrome(s): if len(s) == 1 or s == '': return str(len(s)) + "\n" + s else: if s == s[::-1]: return str(len(s)) + "\n" + s else: for i in range(len(s)-1, 0, -1): for j in range(len(s)-i+1): temp = s[j:j+i] if temp == temp[::-1]: return str(len(temp)) +"\n"+temp 

    Aquí hay otro enfoque limpio y simple tomado del excelente curso en línea Diseño de progtwigs de computadora por P. Norvig. Se itera sobre todos los caracteres de la cadena e intenta “hacer crecer” la cadena hacia la izquierda y hacia la derecha.

     def longest_sub_palindrome_slice(text): "Return (i,j) such that text[i,j] is the longest palindrome in text" if text == '': return (0, 0) def length(slice): a,b = slice; return ba candidates = [grow(text, start, end) for start in range(len(text)) for end in (start, start + 1)] return max(candidates, key=length) def grow(text, start, end): "Start with a 0- or 1- length palindrome; try to grow a bigger one" while (start > 0 and end < len(text) and text[start-1].upper() == text[end].upper()): start -= 1; end += 1 return (start, end) 
     value ="Madamaaamadamaaaacdefgv" longestPalindrome ="" lenght =0; for i in range(len(value)): for j in range(0, i): array = value[j:i + 1] if (array == array[::-1] and len(longestPalindrome) < len(array)): longestPalindrome =array print(longestPalindrome) 
     def longestPalindrome(s): temp = "" for i in range(len(s)): for j in range(len(s)-1,i-1,-1): if s[i] == s[j]: m = s[i:j+1] if m == m[::-1]: if len(temp) <= len(m): temp = m return temp 

    Tengo que aceptar que la solución puede parecer complicada, creo que es la mejor solución para encontrar el palíndromo más grande en una subsecuencia (considerando los caracteres intermedios, por ejemplo, en “carácter”, el palíndromo más grande debe ser carac) es:

     def find_char_backwards(a, c): for i in range(len(a) - 1, -1,-1): if a[i] == c: index=i return True, index return False, 0 def longest_palindorme(a): if len(a) < 2: return a else: c=a[0] (exist_char,index) = find_char_backwards(a[1:],c) if exist_char: palindrome=[c] + longest_palindorme(a[1:index+1]) + [c] else: palindrome=[] rest_palidorme=longest_palindorme(a[1:]) if len(palindrome)>len(rest_palidorme): return palindrome else: return rest_palidorme 

    Cuando a es una matriz, esta solución utiliza la recursión y la progtwigción dinámica.

    Utilice un bucle nested:

     for x in range(len(body)): for y in range(len(body)): ...