plus_grand_bord d'une chaine de caractère

bonjour,

là je commence à :ptdr:
"je suis novice dans la programmation python surtout en ce qui concerne les séquence"

j'ai l'énoncé suivant:

On vous demande d’écrire une fonction plus_grand_bord(w) qui, étant donné un mot w, retourne le plus grand bord de ce mot. On dit qu’un mot u est un bord de w, si u est à la fois un préfixe strict (c’est-à-dire un texte avec la première partie du texte w non vide et non égal à w lui-même) de w et un suffixe strict (c’est-à-dire un texte avec la dernière partie du texte w non vide et non égal à w lui-même) de w. Si w n’a pas de bord, la fonction retourne une chaîne de caractères vide.
Exemple : 'a' et 'abda' sont des bords de 'abdabda'
En effet:

'abdabda' à la fois commence et se termine par 'a'

De même 'abdabda' à la fois commence et se termine par 'abda'('abdabda' et 'abdabda')

Le plus grand bord est 'abda'.


comme proposition j'ai fait:

Code:

---

1 2 3 4 5 6 7 8 9 10

def plus_grand_bord(w): u=input() if (u[0:]!="" and u[0:]!=w) and (u[::]!="" and u[::]!=w): print(u) else: print("")     w= input() plus_grand_bord(w)

---

l'exception "EOFError: EOF when reading a line" se déclenche :calim2:

Salut,

Le plus grand bord possible, c'est quand la chaîne de caractères se répète (abda + abda).
Maintenant, si j'ai "abdaXYabda"...

• je coupe la chaîne en deux et "abdaX" n'est pas Yabda",
• j'enlève le dernier caractère de la premier chaine et le premier de la 2nd

"abda" == "abda" et j'ai fini.
Donc au début on prend les 2 moitiés, on compare et on supprime un caractère à droite ou à gauche et on recommence tant qu'on n'a pas rencontré une égalité ou la chaine vide...

- W

salut,

"{première,dernière} partie du texte w non vide et non égale à w lui-même", je pense qu'on peut même faire une boucle sur la totalité du mot moins un caractère en réalité, c'est ce que semble confirmer le recouvrement avec ("abdabda", "abda")

je verrais un truc comme ça :

Code:

---

1 2 3 4 5

def plus_grand_bord(w): for i in range(len(w)-1, -1, -1): if w[:i] == w[-i:]: break return w[:i]

---

La moitié des itérations ne servent à rien (parce qu'on parle de prefixe/suffixe "stricts"):

Code:

---

1 2 3 4 5

def plus_grand_bord(w): for i in range(len(w)//2, -1, -1): if w[:i] == w[-i:]: break return w[:i]

---

mais si je comprends bien qu'on peut prendre un certain plaisir à faire ce genre d'exo. c'est pas en repartant avec une solution que le P.O apprendra à programmer (donc çà ne l'aide pas vraiment).

-W

pour le mot 'abdabda' ta fonction ne retourne que le premier 'a', perso j'ai compris ça comme le fait qu'elle devrait retourner 'abda' :

Citation:

---

Envoyé par FATENMRABET

(...) 'abdabda' à la fois commence et se termine par 'abda'('abdabda' et 'abdabda')

Le plus grand bord est 'abda'.

---

Citation:

---

Envoyé par BufferBob

pour le mot 'abdabda' ta fonction ne retourne que le premier 'a', perso j'ai compris ça comme le fait qu'elle devrait retourner 'abda' :

---

La question est de savoir si les bords se recouvrent ou pas... Et tel que c'est défini (çà date de Knuth), ils le peuvent (donc j'ai tord) et ton code est juste car si on lui soumet 'aaaa', il sort bien 'aaa'. (c'est strict)

- W

Citation:

---

Envoyé par BufferBob

salut,

"{première,dernière} partie du texte w non vide et non égale à w lui-même", je pense qu'on peut même faire une boucle sur la totalité du mot moins un caractère en réalité, c'est ce que semble confirmer le recouvrement avec ("abdabda", "abda")

je verrais un truc comme ça :

Code:

---

1 2 3 4 5

def plus_grand_bord(w): for i in range(len(w)-1, -1, -1): if w[:i] == w[-i:]: break return w[:i]

---

---

salut,
merci pour votre aide mais est ce que vous pouvez m'expliquer cette ligne

Code:

---

for i in range(len(w)-1, -1, -1):

---

Citation:

---

Envoyé par wiztricks

Salut,

Le plus grand bord possible, c'est quand la chaîne de caractères se répète (abda + abda).
Maintenant, si j'ai "abdaXYabda"...

• je coupe la chaîne en deux et "abdaX" n'est pas Yabda",
• j'enlève le dernier caractère de la premier chaine et le premier de la 2nd

"abda" == "abda" et j'ai fini.
Donc au début on prend les 2 moitiés, on compare et on supprime un caractère à droite ou à gauche et on recommence tant qu'on n'a pas rencontré une égalité ou la chaine vide...

- W

---

salut,
oui je comprend, c'est le principe de recherche dichotomique en algorithmique merci :oops:

Citation:

---

Envoyé par wiztricks

La moitié des itérations ne servent à rien (parce qu'on parle de prefixe/suffixe "stricts"):

Code:

---

1 2 3 4 5

def plus_grand_bord(w): for i in range(len(w)//2, -1, -1): if w[:i] == w[-i:]: break return w[:i]

---

mais si je comprends bien qu'on peut prendre un certain plaisir à faire ce genre d'exo. c'est pas en repartant avec une solution que le P.O apprendra à programmer (donc çà ne l'aide pas vraiment).

-W

---

salut,
oui je comprend bien c'est clair maintenant merci

Citation:

---

Envoyé par BufferBob

pour le mot 'abdabda' ta fonction ne retourne que le premier 'a', perso j'ai compris ça comme le fait qu'elle devrait retourner 'abda' :

---

salut,
merci pour votre temps, oui c'est ça