Forum Programmation.autre Repérer des chaines doubles

Posté par zedS le 25 octobre 2019 à 08:20. Licence CC By‑SA.

Étiquettes : aucune

oct.

2019

Bonjour,

Je cherche à supprimer des doublons dans une chaine de caractère, sachant que les doublons se suivent toujours.
Genre de chaine avec doublon :
- la lo li lulu (je veux que lulu devienne lu)
- 0.550.55 (je veux ne garder qu'un seul 0.55)
- 0.80.8 (je veux ne garder qu'un seul 0.8)

Je ne vois absolument pas comment faire ça, quelqu'un a une petit idée ?

Pour info, le langage que j'utilise est PHP mais peu importe le langage, c'est vraiment l'algo que je n'arrive pas à trouver (utilisation expression régulière, analyse séquentiel des caractères …)

# Incohérence dans les exemples

Posté par lolop (site web personnel) le 25 octobre 2019 à 08:40. Évalué à 3.
- la lo li lulu (je veux que lulu devienne lu)
- 0.550.55 (je veux ne garder qu'un seul 0.55)
- 0.80.8 (je veux ne garder qu'un seul 0.8)
Si j'applique la réduction du 1er exemple au 2ème, le 55 aurait du devenir 5… J'en conclues qu'il faut réduire les doublons les plus grands et s'arrêter dès qu'on a fait une réduction. Tu pars donc d'une sous-chaine égale à la moitié de ta chaine et cherche les doublons, puis tu itères en réduisant la sous-chaine d'un caractère à chaque fois. Et tu stoppes dès que tu as pu faire une réduction.
Le passage au code est laissé pour exercice.

Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN
- [^] # Re: Incohérence dans les exemples
  
  Posté par Sytoka Modon (site web personnel) le 25 octobre 2019 à 10:21. Évalué à 3.
  
  Yep, ça sent effectivement l'exercice de cours à 10 km ;-)
  - [^] # Re: Incohérence dans les exemples
    
    Posté par Anthony Jaguenaud le 25 octobre 2019 à 10:47. Évalué à 2.
    
    Je sais pas, ça manque de contexte, mais le compte de zedS est vieux de 2010 il a déjà un journal et plusieurs demande de forum…
    - [^] # Re: Incohérence dans les exemples
      
      Posté par zedS le 25 octobre 2019 à 14:41. Évalué à 2. Dernière modification le 25 octobre 2019 à 14:42.
      :)
      Non ce n'est pas un exercice et la réponse de Lolop me va. Merci
      
      Les valeurs doubles sont jointes et dans tout les cas il y'a des espace autour donc divisé la chaine en deux et voir ci c'est indique devrait fonctionner. J'ai tout simplement pas assez réflechi …
      Ci-dessous le bout de code (tout moche) qui fonctionne :
      
      <?php $strs =array('la lo li lulu', '0.550.55', '0.80.8'); foreach($strs as $str){ foreach(explode(' ', $str) as $word){ $wlen = strlen($word); if($wlen%2 == 0 && (substr($word,0, $wlen/2) == substr($word,$wlen/2) )) echo "\nIl y a un double dans la chaine '$str' : ".substr($word, 0, $wlen/2); } } ?> qui donne Il y a un double dans la chaine 'la lo li lulu' : lu Il y a un double dans la chaine '0.550.55' : 0.55 Il y a un double dans la chaine '0.80.8' : 0.8
      - [^] # Re: Incohérence dans les exemples
        
        Posté par Kerro le 25 octobre 2019 à 19:07. Évalué à 3. Dernière modification le 25 octobre 2019 à 19:07.
        
        dans tout les cas il y'a des espace autour
        
        Je ne vois pas d'espace dans « 0.550.55 », donc pas de réduction possible ?
# regex

Posté par vmagnin (site web personnel) le 25 octobre 2019 à 10:51. Évalué à 4.

Je partirai sur une expression régulière pour rechercher (.+)\1 et le remplacer par \1

A affiner. Tu peux tester par exemple dans Kate pour mettre au point l'expression.
- [^] # Re: regex
  
  Posté par _kaos_ le 25 octobre 2019 à 11:27. Évalué à 1.
  
  Salut,
  
  Moi absolument pas :)
  
  Comme l'a déjà noté lolop l'énoncé peut prêter à confusion. on fait quoi du 0.550.55, on le réduit en 0.5 ? 0.55 ?
  
  S'il n'y a pas de règle formelle, les regexps vont être un casse-tête infernal.
  
  Matricule 23415
  - [^] # Re: regex
    
    Posté par vmagnin (site web personnel) le 25 octobre 2019 à 14:53. Évalué à 3.
    
    C'est une question d'avidité de la regex. Il faudrait regarder dans le détail le fonctionnement. Mais en utilisant les regex de mon éditeur Kate, voici ce que j'obtiens.
    
    J'ai copié/collé le texte suivant, y compris les remarques entre parenthèses :
    - la lo li lulu (je veux que lulu devienne lu) - 0.550.55 (je veux ne garder qu'un seul 0.55) - 0.80.8 (je veux ne garder qu'un seul 0.8)
    
    En cherchant (.+)\1 et en remplaçant par \1, j'obtiens :
    
    - la lo li lu (je veux que lu deviene lu) - 0.55 (je veux ne garder qu'un seul 0.5) - 0.8 (je veux ne garder qu'un seul 0.8)
    
    Le moteur de regex est avide par défaut et on obtient ce que demande zedS. A voir si ça se comporte pareil en PHP.
    - [^] # Re: regex
      
      Posté par zedS le 25 octobre 2019 à 15:09. Évalué à 1.
      
      Cela fonctionne bien en php avec preg_replace().
      je comprend pas trop, mais ça fonctionne :)
      Merci
      - [^] # Re: regex
        
        Posté par vmagnin (site web personnel) le 25 octobre 2019 à 15:20. Évalué à 3. Dernière modification le 25 octobre 2019 à 15:23.
        
        La parenthèse (.+) représente un bloc d'au moins (exprimé par le plus) un caractère (symbolisé par le point). Le \1 représente une répétition de ce bloc (numéro 1), juste à la suite.
        
        Comme on remplace le tout par simplement \1, le doublon est supprimé.
        
        Enfin, par défaut l'expression régulière est avide, c'est-à-dire qu'elle cherche le plus grand bloc possible qui correspond. Ce qui lui évite par exemple de remplacer 55 par 5.
      - [^] # Re: regex
        
        Posté par vmagnin (site web personnel) le 25 octobre 2019 à 15:29. Évalué à 3.
        
        Un très bon livre sur les expressions régulières :
        Introduction aux expressions régulières - Avec awk, Java, Perl, Python, PHP, Tcl… de Bernard Desgraupes
      - [^] # Re: regex
        
        Posté par vmagnin (site web personnel) le 25 octobre 2019 à 15:44. Évalué à 2. Dernière modification le 25 octobre 2019 à 15:46.
        
        Attention, ça ne détecte que les doublons, pas les triplets, quadruplets, etc.
        Pour ça il faudrait, je pense (et ça a l'air de fonctionner), écrire (.+)\1+
        ce qui signifie "au moins une répétition".

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.