La longueur de la plus longue sous-séquence commune de deux chaînes

Question

J'essaye d'écrire une fonction qui calcule la longueur de la plus longue sous-séquence commune des deux chaînes d'entrée str1 et str2.

C'est ce que j'ai en ce moment,

(define LCS 
    (lambda (str1 str2) 
    (if (OR (equal? str1 "") (equal? str2 "")) 
     0 
     (if (equal? (string-contains str1 (string-ref str2 0)) #t) 
      (+ 1 (LCS (substring str1 1 (string-length str1)) 
         (substring str2 1 (string-length str2)))) 
      (LCS (substring str1 1 (string-length str1)) 
       (substring str2 1 (string-length str2))))))) 

Où string-contains retours vrai si une chaîne a un certain caractère en elle. À l'heure actuelle, il semble que cela fonctionne, mais je pense qu'il pourrait y avoir un bug.

Answer 1

Votre code est totalement sur la bonne voie si un algorithme relativement lent ne vous dérange pas; il y a une approche plus sophistiquée du problème, avec une programmation dynamique, si vous en avez besoin pour être plus rapide. À l'heure actuelle, le bogue dans votre code est que vous descendez la longueur des deux chaînes simultanément avec chaque appel récursif. Il échouerait, par exemple (je pense, je ne l'ai pas essayé) avec les deux chaînes suivantes: (LCS "scheme" "emesch") Raison étant que les sous-chaînes correspondantes ne commencent pas à la même position dans les première et deuxième chaînes. Je suggère que vous divisiez la récursion en deux appels récursifs: l'un où vous supprimez un caractère à l'avant de la première chaîne, et l'autre où vous supprimez un caractère à l'avant de seulement la seconde. Ensuite, vous prenez le meilleur résultat de l'un ou l'autre de ces appels. De cette façon, vous pouvez être sûr que vous trouverez des sous-chaînes, peu importe où elles se trouvent dans l'autre chaîne.

Answer 2

Les deux chaînes sont analysées en parallèle. Si les deux caractères actuels sont identiques, la longueur de la sous-séquence commune la plus longue augmente de un, et l'analyse continue au caractère suivant dans chaque chaîne; sinon, il y a deux possibilités à considérer récursivement, après avoir supprimé le caractère courant d'une séquence d'entrée ou d'une autre, et la longueur de la plus longue sous-séquence commune est simplement la plus grande des deux possibilités.

Une explication plus complète et une implémentation dans Scheme sont disponibles sur mon blog.