human
Pouvez-vous implémenter l'algorithme KMP avec Python
gpt
L'algorithme de Knuth-Morris-Pratt (ou algorithme KMP) est un algorithme de recherche de chaîne qui recherche les occurrences d'un "mot" W dans une chaîne principale "texte" S en utilisant l'observation qu'en cas de désaccord, le mot lui-même contient suffisamment d'informations pour déterminer où pourrait commencer la prochaine correspondance, évitant ainsi la réexamination des caractères déjà correspondants.

```
# Programme Python3 pour l'algorithme KMP
class KMP:
    def partiel(self, motif):
        """ Calculer la table de correspondance partielle: Chaîne -> [Int]"""
        ret = [0]
        
        for i in range(1, len(motif)):
            j = ret[i - 1]
            while j > 0 and motif[j] != motif[i]:
                j = ret[j - 1]
            ret.append(j + 1 if motif[j] == motif[i] else j)
        return ret
        
    def recherche(self, T, P):
        """ 
        Algorithme principal de recherche KMP: Chaîne -> Chaîne -> [Int] 
        Renvoie toutes les positions correspondantes de la chaîne de motif P dans T
        """
        partiel, ret, j = self.partiel(P), [], 0
        
        for i in range(len(T)):
            while j > 0 and T[i] != P[j]:
                j = partiel[j - 1]
            if T[i] == P[j]: j += 1
            if j == len(P): 
                ret.append(i - (j - 1))
                j = partiel[j - 1]
            
        return ret

kmp = KMP()
txt = "abdabeabfabc"
pat = "abc"
kmp.recherche(txt, pat)
```

La sortie du code ci-dessus est:

```
9
```

La complexité temporelle de cet algorithme est O(N) et l'espace auxiliaire nécessaire pour KMP est O(M).