Cette méthode de sous-chaîne commune la plus longue est-elle correcte ?

Question

J'ai trouvé un algorithme pour Sous-chaîne commune la plus longue.Cela se fait généralement en utilisant dynamic programming, en utilisant un tableau 2D de taille mxn où m et n sont les longueurs des deux chaînes considérées.

Je vais construire la matrice suivante pour les deux chaînes.

M[i][j] = 1 if s1[i]==s2[j] else 0.

Par exemple, si les chaînes sont : abcxy et pqaabx

La matrice se présente comme suit :

    a b c x y
 p  0 0 0 0 0
 q  0 0 0 0 0
 a  1 0 0 0 0
 a  1 0 0 0 0
 b  0 1 0 0 0
 x  0 0 0 1 0

Maintenant, je recherche une séquence continue maximale de 1s dans chaque diagonale allant du haut à gauche vers le bas à droite.

La valeur maximale parmi celles-ci sera la réponse.

Je peux effectuer l'opération ci-dessus sans utiliser explicitement le tableau.La complexité temporelle est toujours O(M*N).Il n’y a donc pas besoin de mémoire.

Quelqu'un peut-il m'indiquer où je me trompe ?

Answer 1

Votre méthode est correcte.Pour preuve, supposons que la sous-chaîne commune la plus longue pour S1 et S2 provenait de S1[i..j] et S2[p..q].Cela implique s1 [i + k] = s2 [p + k

Ceux-ci se trouvent tous sur la diagonale commençant par (i,p).

La solution de programmation dynamique fait la même chose, mais au lieu de calculer d'abord la table et de parcourir des chemins diagonaux, elle calcule la table en fonction de son parent diagonal et de leur correspondance ou non.

ÉDITÉ

Sur votre commentaire sur la solution Wikipédia utilisant de la mémoire supplémentaire.C'est là uniquement pour plus de clarté.En principe, vous n'avez besoin que de deux lignes de la matrice dans la solution Wikipédia et conservez le nombre maximum actuel dans une variable.C'est correct puisque pour toute (i,j)ième entrée dans la matrice

M(i,j) = 1 + M(i-1, j-1) (si s1[i] == s2[j])

comme vous pouvez le voir, les éléments de la ligne actuelle dépendent uniquement des éléments de la ligne immédiatement supérieure.

Answer 2

Votre algorithme est correct, mais l'approche DP standard élimine votre deuxième phase et simplifie la solution.

Au lieu de marquer des valeurs booléennes puis de scanner les diagonales pour rechercher les séquences les plus longues, vous pouvez calculer les longueurs des diagonales au fur et à mesure que vous construisez la matrice. Une seule passe est requise.

En termes de complexité temporelle et spatiale, les deux solutions sont O(NxM).Votre solution peut économiser de la mémoire si vous utilisez une représentation matricielle binaire, tandis que l'autre solution est probablement légèrement plus rapide.