Implémentez une fonction pour trouver la plus longue sous-séquence commune de deux chaînes.

Implémentez une fonction pour trouver la plus longue sous-séquence commune de deux chaînes.

Pour implémenter une fonction qui trouve la plus longue subséquence courante (LCS) de deux chaînes, nous utiliserons la programmation dynamique, qui est l'approche la plus efficace pour ce problème. Voici une implémentation étape par étape dans Python:

 <code class="python">def longest_common_subsequence(str1, str2): m, n = len(str1), len(str2) # Create a table to store results of subproblems dp = [[0] * (n 1) for _ in range(m 1)] # Build the dp table for i in range(1, m 1): for j in range(1, n 1): if str1[i-1] == str2[j-1]: dp[i][j] = dp[i-1][j-1] 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # The last cell contains length of LCS return dp[m][n] # Test the function str1 = "AGGTAB" str2 = "GXTXAYB" print("Length of LCS is", longest_common_subsequence(str1, str2)) # Output: Length of LCS is 4</code>

Cette fonction utilise une table de programmation dynamique 2D pour calculer efficacement la longueur des LC entre str1 et str2 . La complexité du temps est O (M n), et la complexité de l'espace est O (M n), où M et N sont les longueurs des chaînes d'entrée.

Quels sont les algorithmes clés utilisés pour résoudre le plus long problème de sous-séquence commun?

Les algorithmes clés utilisés pour résoudre le plus long problème de sous-séquence commun sont:

1. Programmation dynamique : il s'agit de la méthode la plus couramment utilisée et efficace. Il s'agit de créer une table pour stocker les résultats des sous-problèmes et de construire la solution de manière itérative. L'idée de base est de remplir une matrice où dp[i][j] représente la longueur des LC des sous-chaînes str1[0..i-1] et str2[0..j-1] .
2. Recursion : Une approche naïve du problème LCS est par la récursivité, mais elle est inefficace en raison du calcul répété des mêmes sous-problèmes. L'approche récursive suit le principe de décomposition du problème en sous-problèmes plus petits, mais sans stocker des résultats intermédiaires, il se traduit par une complexité temporelle exponentielle.
3. Mémuisation : Il s'agit d'une optimisation sur l'approche récursive, où les résultats des sous-problèmes sont stockés pour éviter les calculs redondants. La mémorisation transforme efficacement la solution récursive en une solution de programmation dynamique, réduisant la complexité temporelle au polynôme.
4. Backtracking : Bien qu'il ne soit généralement pas utilisé seul pour résoudre le problème du LCS en raison de son inefficacité, le retour en arrière peut être utilisé pour reconstruire le LCS une fois que sa longueur est connue grâce à une programmation ou à une mémorisation dynamique.

Comment s'améliorer l'efficacité de la plus longue fonction de subséquence commune?

L'efficacité de la plus longue fonction de subséquence commune peut être améliorée de plusieurs manières:

1. Optimisation de l'espace : l'implémentation d'origine utilise l'espace o (m * n), mais il est possible de réduire la complexité de l'espace à O (n) en gardant uniquement la trace de deux lignes de la table de programmation dynamique à tout moment.

    <code class="python">def optimized_lcs(str1, str2): m, n = len(str1), len(str2) prev = [0] * (n 1) curr = [0] * (n 1) for i in range(1, m 1): for j in range(1, n 1): if str1[i-1] == str2[j-1]: curr[j] = prev[j-1] 1 else: curr[j] = max(curr[j-1], prev[j]) prev, curr = curr, prev # Swap the rows return prev[n]</code>

2. Utilisation de l'algorithme de Hirschberg : si nous devons trouver le LCS réel plutôt que sa longueur, l'algorithme de Hirschberg peut être utilisé pour trouver le LCS dans le temps O (M * N) et l'espace O (min (M, N)), qui est plus efficace dans l'espace que l'approche de programmation dynamique traditionnelle.
3. Parallélisation : Le calcul de la table de programmation dynamique peut être parallélisé dans une certaine mesure, en particulier si vous travaillez avec de grandes chaînes, en divisant le travail entre plusieurs processeurs ou threads.
4. Algorithmes spécialisés : pour des types spécifiques de chaînes, des algorithmes plus spécialisés peuvent être plus efficaces, par exemple, lorsqu'ils traitent des séquences d'ADN, certains algorithmes bioinformatiques optimisés pour ces entrées pourraient être utilisés.

Quelles sont les applications courantes de la recherche de la plus longue subséquence commune dans les scénarios du monde réel?

Trouver la plus longue sous-séquence commune est un algorithme polyvalent utilisé dans diverses applications du monde réel, notamment:

1. Bioinformatique : Dans la génétique et la biologie moléculaire, LCS est utilisé pour comparer les séquences d'ADN pour trouver des similitudes et des différences. Par exemple, il peut aider à aligner les séquences génétiques pour identifier les mutations ou les similitudes chez différentes espèces.
2. Comparaison du texte et contrôle de la version : LCS est fondamental dans les outils utilisés pour la comparaison des fichiers, tels que les outils DIFF dans les systèmes de contrôle de version comme Git. Il aide à identifier les modifications et à fusionner différentes versions du code source ou des documents.
3. Détection du plagiat : En trouvant le LCS entre deux documents, il est possible d'identifier les plus longs segments courants qui pourraient indiquer le plagiat.
4. Compression des données : Dans les algorithmes de compression de données, les LC peuvent être utilisés pour identifier les séquences de données redondantes qui peuvent être représentées plus efficacement.
5. Reconnaissance de la parole : LCS peut être utilisé pour aligner et comparer les séquences de mots parlées, ce qui est utile pour améliorer la précision de la conversion de la parole à texte.
6. Traitement du langage naturel : LCS est utilisé dans les tâches NLP telles que la mesure de la similitude du texte, qui peut être appliquée à l'optimisation des moteurs de recherche, à l'analyse des sentiments et à la traduction automatique.

Ces applications exploitent la puissance des LC pour résoudre des problèmes complexes en identifiant efficacement des similitudes dans les séquences, fournissant ainsi des informations précieuses et facilitant des techniques de traitement avancées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!