Reconstruction de l'algorithme de Knuth-Morris-Pratt (en)

L'algorithme de recherche de chaîne Knuth-Morris-Pratt est à mon avis un de ces algorithmes magiques qui reste difficile à comprendre ou à expliquer sans vraiment rentrer dans les détails. Ici, on cherche à comprendre comment cet algorithme a pu être inventé, en raffinant une solution naïve petit à petit.