Sous-chaîne commune la plus longue en Python

1. Sous-chaîne commune la plus longue en Python
2. Sous-chaîne commune la plus longue utilisant des boucles en Python
3. Utilisez la récursivité pour trouver la plus longue sous-chaîne commune
4. Utiliser la programmation dynamique pour trouver la plus longue sous-chaîne commune en Python
5. Conclusion

String en Python stocke une séquence de caractères pour y effectuer diverses opérations. Les sous-chaînes font partie de ces chaînes.

Dans cet article, nous devons trouver la plus longue sous-chaîne commune entre deux chaînes données et discuterons de différentes solutions pour la même chose.

Sous-chaîne commune la plus longue en Python

Une sous-chaîne est une séquence contiguë de caractères dans une chaîne donnée. Il peut être de n’importe quelle longueur.

Le problème principal est que nous avons reçu deux chaînes, et nous devons trouver une sous-chaîne commune entre les chaînes données et qui devrait être la plus longue parmi toutes les sous-chaînes communes possibles.

Input: str1 = "HaveAAppleRegularly"
       str2 = "HaveAnAnApple"
Output: "Apple"

Dans l’exemple ci-dessus, nous avons deux sous-chaînes communes entre les chaînes données, "Have" et "Apple". Mais puisque la longueur de la sous-chaîne "Apple" est la plus longue parmi les autres sous-chaînes ; par conséquent, il sera affiché comme notre résultat.

Ce problème peut être résolu en utilisant divers concepts comme la récursivité et la programmation dynamique.

Sous-chaîne commune la plus longue utilisant des boucles en Python

Les boucles peuvent être utilisées pour parcourir une chaîne. Nous pouvons parcourir la chaîne ici en utilisant les boucles et trouver notre plus longue sous-chaîne commune entre les deux chaînes données.

Nous utiliserons les boucles for et while dans cette approche. Voici les étapes à suivre pour trouver la plus longue sous-chaîne commune en Python.

Exemple de code :

str1 = "PokemonGo"
str2 = "StopPokemonLetsGo"
result = 0
for i in range(len(str1)):
    for j in range(len(str2)):
        k = 0
        while (
            (i + k) < len(str1) and (j + k) < len(str2) and str1[i + k] == str2[j + k]
        ):
            k = k + 1
        result = max(result, k)

print("Length of the longest common substring is:", result)

Production:

Length of the longest common substring is: 7

Toutes les sous-chaînes de la chaîne peuvent être calculées en temps O(n^2), alors que vérifier que si la sous-chaîne courante correspond à une sous-chaîne de la deuxième chaîne prendrait un temps O(m). La complexité temporelle de l’approche ci-dessus serait O(n^2 * m) où n et m sont respectivement les longueurs des deux chaînes données.

Cependant, comme nous n’avons pas pris d’espace supplémentaire pour réaliser la solution, la complexité spatiale pour la solution ci-dessus serait O(1).

Utilisez la récursivité pour trouver la plus longue sous-chaîne commune

La récursivité fait référence à une fonction qui s’appelle elle-même. Nous avons besoin d’un cas de base et du diagramme de choix pour le problème en question dans la récursivité.

Nous suivrons les étapes ci-dessous pour trouver la plus longue sous-chaîne commune en Python.

Exemple de code :

def LCS(s1, s2, n, m):
    if n == 0 or m == 0:
        return 0

    if s1[n - 1] == s2[m - 1]:
        return 1 + lcs(s1, s2, n - 1, m - 1)

    else:
        return max(lcs(s1, s2, n, m - 1), lcs(s1, s2, n - 1, m))


s1 = "pokemonGo"
s2 = "watchPokemon"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)

Production:

Length of the longest common substring is: 7

La complexité temporelle de la solution ci-dessus serait O(3^(m+n)), et la complexité spatiale serait O(m+n).

Utiliser la programmation dynamique pour trouver la plus longue sous-chaîne commune en Python

L’idée de base de la programmation dynamique est de trouver les longueurs de toutes les sous-chaînes des deux chaînes et de stocker leurs longueurs respectives dans une table. Depuis l’utilisation de la récursivité, il est possible d’obtenir une erreur de débordement de pile car, pour les entrées volumineuses, la pile de récursivité continuera d’augmenter.

Nous introduisons le concept de programmation dynamique dans lequel nous formons une table et continuerons à stocker les résultats pour les sous-chaînes respectives. Le même algorithme que nous avons utilisé dans la récursivité est également utilisé avec quelques modifications.

Maintenant, nous allons discuter des étapes pour trouver la plus longue sous-chaîne commune en Python.

Exemple de code :

def LCS(X, Y, m, n):

    dp = [[0 for x in range(m + 1)] for y in range(n + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]


s1 = "playbatball"
s2 = "batballwicket"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)

Production:

Length of the longest common substring is: 7

Puisqu’il n’y a que deux boucles dans notre solution, la complexité temporelle de la solution ci-dessus serait O(m*n). Nous utilisons de l’espace supplémentaire en formant un tableau pour stocker les résultats.

La complexité spatiale de la solution ci-dessus serait O(m*n).

Conclusion

Nous avons appris trois approches différentes pour trouver la plus longue sous-chaîne commune entre deux chaînes données. La première approche, une approche naïve, utilise trois boucles et trouve toutes les sous-chaînes de la chaîne donnée et contrôle la plus longue parmi toutes les sous-chaînes.

La deuxième approche utilise la récursivité, tandis que la troisième approche utilise la programmation dynamique pour trouver la plus longue sous-chaîne commune en Python. La troisième approche serait la plus rapide parmi toutes les solutions abordées dans cet article pour résoudre le problème et devrait être préférée.