Python: la recherche de la plus longue des palindromes l'intérieur d'un mot et de palindromes à l'intérieur d'un mot/string

Voici donc le code que j'ai écrit à trouver des palindromes l'intérieur d'un mot (Pour vérifier si il y a des palindromes intérieur d'un mot, y compris le mot lui-même)
Condition: les espaces entre les caractères sont comptés et pas ignoré
Exemple: Un mais le tuba est un palindrome, mais, techniquement, en raison des espaces concernés maintenant il ne l'est pas. donc, c'est le critère.

Basé sur la ci-dessus, le code suivant devrait normalement travailler. Vous pouvez essayer sur votre propre avec différents tests pour vérifier si ce code donne aucune erreur.

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

Et ici est une ancienne version de celui-ci. Ce que je veux dire c'est que j'ai essayé de commencer à partir du milieu et de détecter les palindromes par itération à partir du début et de vérification pour chaque supérieures et inférieures des indices de caractère en vérifiant si elles sont égales caractères. si ils sont ensuite je vérifie si c'est un palindrome comme un palindrome vérifier.
voici ce que j'ai fait

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<0:
dec = 0
if inc > 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

findlet() amusant:

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

Parfois cela fonctionne:

pal('madem')
dec -1, inc 1,
text[dec:inc+1] 
s m 
dec 1, inc 3,
text[dec:inc+1] ade
break 1st elif
s m 
dec 2, inc 4,
text[dec:inc+1] dem
break 1st elif
s m 
dec 3, inc 5,
text[dec:inc+1] em
break 1st elif
s m 
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] d d
s d d 
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
s d 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'])

Et sur la base des Critères/Conditions que j'ai mis:

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] 
s a ca 
dec 1, inc 3,
text[dec:inc+1]  ca
break if
s a 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
s a 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]  a 
s  a  
dec 5, inc 9,
text[dec:inc+1] , a m
break else
s r, 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] a m
break else
s  a ma 
dec 5, inc 11,
text[dec:inc+1] , a man
break else
s r, 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
s r 
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
s a 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
s c 
dec 1, inc 3,
text[dec:inc+1]  ca
break if
s a 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
s a man, a 
dec 6, inc 15,
text[dec:inc+1]  a man, a 
s  a man, a  
dec 5, inc 16,
text[dec:inc+1] , a man, a m
break else
s r, 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
s a 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
s c 
dec 1, inc 3,
text[dec:inc+1]  ca
break if
s a ca 
dec 13, inc 15,
text[dec:inc+1]  a 
s  a  
dec 12, inc 16,
text[dec:inc+1] , a m
break 1st elif
s man, a m 
dec 8, inc 17,
text[dec:inc+1]  man, a ma
break 1st elif
s a man, a ma 
dec 6, inc 18,
text[dec:inc+1]  a man, a mar
break 1st elif
s r, 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
s a car, a man, a maraca 
dec 14, inc 16,
text[dec:inc+1] a m
break 1st elif
s man, a m 
dec 8, inc 17,
text[dec:inc+1]  man, a ma
break 1st elif
s a man, a ma 
dec 6, inc 18,
text[dec:inc+1]  a man, a mar
break 1st elif
s r, 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
s a car, a man, a maraca 
dec 15, inc 17,
text[dec:inc+1]  ma
break 1st elif
s a ma 
dec 13, inc 18,
text[dec:inc+1]  a mar
break 1st elif
s r, 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
s a car, a man, a maraca 
dec 16, inc 18,
text[dec:inc+1] mar
break 1st elif
s r, 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
s a 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
s a 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
s a 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
s a 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
s  a man, a maraca. 
dec 5, inc 23,
text[dec:inc+1] , a man, a maraca.
break else
s r, 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
s a car, a man, a maraca. 
Out[8]: ((13, 16), ' a ', ['', ' a ', 'c', ' ', 'aca', 'ara', 'r'])

Parfois, il ne fonctionne pas du tout:

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

Envisagent maintenant de madame est un très joli palindrome, il doit travailler et il y a beaucoup de cas qui je n'ai pas testé moi-même pour savoir ce que les autres légitime palindromes il n'est pas détecter.

Q1: Pourquoi est-il parfois de ne pas détecter?

Q2: je voudrais optimiser mon deuxième code pour cette question. Toutes les entrées?

Q3: Quelle meilleure approche pour un beaucoup beaucoup plus efficace que le code de mon Premier code qui parcourt beaucoup une fois?

InformationsquelleAutor user2290820 | 2013-06-20

palindrome python

15

Votre solution me semble un peu compliqué pour moi. Il suffit de regarder toutes les sous-chaînes et de les vérifier individuellement:
```
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() trouverez uniquement la première occurrence du plus long palindrome, donc si vous voulez le dernier, le remplacer par text.rindex().
- Oui c'est salissant esp. pour le 2ème code où j'ai essayé à l'aide de la touche func findlet() à la recherche de tous les indices d'une lettre dans un mot.j'ai trop compliqué. Superbe
- bien que je l'ai fait comprendre que je n'avais qu'à changer d'énumérer(word) pour range(len(mot)) ce qui rend votre code et mon 1er code le même.donc je suppose que mal de regarder dehors pour des solutions plus efficaces s'il y a
InformationsquelleAutor Blender
1

La fonction suivante renvoie le plus long palindrome contenues dans une chaîne donnée. Il est légèrement différent en ce qu'il utilise itertools comme suggéré dans cette réponse. Il y a une valeur dans l'abstraction de la combinaison de la génération. Sa complexité temporelle est évidemment encore cubes. Il peut trivialement être adaptés en fonction des besoins retour à l'index et/ou la liste de palindromes.
```
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
```
- que faire si j'ai besoin de tous le plus long palindrome . Actuellement , son retour un seul plus long palindrome.
InformationsquelleAutor A-B-B

ci-dessous est un code que j'ai écrit pour la même question. Il pourrait ne pas être vraiment optimisé, mais fonctionne comme un charme. Assez facile à comprendre pour les débutants

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

InformationsquelleAutor Deepanshu Sharma

0
```
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))
```
- Code seulement les réponses ne sont pas très utiles sur leur propre. Il serait utile si vous pouviez ajouter quelques détails expliquant comment/pourquoi il répond à la question.
- Bien que ce code peut aider à résoudre le problème, ça n'explique pas pourquoi et/ou comment il répond à la question. La fourniture de ce contexte supplémentaire permettrait d'améliorer de façon significative à long terme sa valeur éducative. Veuillez modifier votre réponse pour ajouter des explications, y compris quelles sont les limites et les hypothèses s'appliquent.
InformationsquelleAutor Gaurav Padgilwar

Si vous aimez la solution récursive, j'ai écrit une version récursive. Il est également intuitive.

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

InformationsquelleAutor Abhishek Mishra

Voici un code que vous pouvez utiliser pour trouver le plus long palindrome de sous-chaîne:

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)

en donnant juste le code, sans aucune explication ne satisfaire de débordement de pile dans les normes

InformationsquelleAutor senthil balaji

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

InformationsquelleAutor Suraj Dubal

J'ai fait le nom de la fonction en tant que maxpalindrome(s) dans ce un argument chaîne de caractères "s". Cette fonction retourne la plus longue possible palindrome sous-chaîne et de la longueur de la sous-chaîne...

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

c'est une même solution de ci-dessus

InformationsquelleAutor Manish kumar

Ici est un autre chiffon propre et simple de l'approche de l'excellent cours en ligne La conception des Programmes d'Ordinateur par P. Norvig. Il itère sur tous les caractères de la chaîne et des tentatives de "pousser" la chaîne à la fois à gauche et à droite.

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 b-a
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)

InformationsquelleAutor msilb

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)

InformationsquelleAutor Ankit Gupta

HTML:

s='stresseddesserts'
out1=[]
def substring(x):
for i in range(len(x)):
a=x[i:]
b=x[:-i]
out1.append(a)
out1.append(b)
return out1
for i in range(len(s)):
substring(s[i:])    
final=set([item for item in out1 if len(item)>2])
final
palind={item:len(item) for item in final if item==item[::-1]}
print(palind)
sorted(palind.items(),reverse=True, key=lambda x: x[1])[0]

{'tresseddessert': 14, 'seddes': 6, 'esseddesse': 10, 'esse': 4, 'stresseddesserts': 16, 'resseddesser': 12, 'eddé': 4, 'sseddess': 8}

('stresseddesserts', 16)

InformationsquelleAutor ashish bansal

-1
```
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
```
- Alors que ce code peut répondre à la question, en fournissant plus de contexte sur comment et/ou pourquoi il résout le problème serait d'améliorer la réponse à long terme de valeur.
InformationsquelleAutor Muskaan

-2

Je suis d'accord, la solution peut sembler compliqué, je pense que la meilleure solution, de trouver le plus grand palindrome dans une sous-suite, (en tenant compte de caractères entre, par exemple, dans "caractère" le plus grand palindrome devrait être ccrac) est:

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

Où a est une matrice, cette solution utilise la récursivité, et de la programmation dynamique

InformationsquelleAutor Magic Lui

-3

Utiliser une boucle imbriquée:
```
for x in range(len(body)):
for y in range(len(body)):
...
```
- Cela peut faire quelque chose, mais il n'est pas clair du tout la façon dont il traite la question en quelque sorte.
InformationsquelleAutor Bob

Vous devez vous connecter pour publier un commentaire.