Discussion:Algorithme de Knuth-Morris-Pratt

Indentation

J'ai indenté le code source de l'implémentation C de l'algorithme, il était affreux, voici la version :

int kmp_recherche(char *P, char *S)
{
    extern int T[];
    int m = 0;
    int i = 0;

    while (S[m + i] != '\0' && P[i] != '\0')   // Tant que l'on a pas atteint la fin de la chaîne S ou de la chaîne P.
    {
        if (S[m + i] == P[i])
        {
                              // Si on a encore une correspondance
            ++i;              // alors on regarde la lettre suivante
        }
        else
        {
            // sinon
            m += i - T[i];    /* la prochaine correspondance partielle possible est à T[i] lettre avant celle
                              * qu'on vient de regarder. */

            if (i > 0)
                i = T[i];     /* Puisque l'on sait que les T[i]-1 premières lettres à partir de m sont bonne,
						            * il suffit de regarder P a partir de la T[i]ème position. Pour S on peut
                              * remarquer que on m+i est maintenant égale à (m+i-T[i])+(T[i]) avec les
                              * anciennes valeurs. Ce qui montre qu'on ne retourne pas en arrière. */
        }
    }

    //Quand on a fini de parcourir une des deux chaines
    if (P[i] == '\0')
    {
        //si la chaine finie est P alors on a trouvé une correspondance à la place m
        return m;
    }
    else
    {                      /* Sinon c'est qu'il n'existe pas de correspondance de P dans S donc on renvoie
                           * un nombre impossible */
        return m + i;      /* m est forcément le nombre de caractère de S, donc m+1 est impossible. On
                           * pourrait aussi renvoyer -1 */
    }
}

remarques sur l'algo naïf

L'algo naïf a plutôt sa place dans l'article Algorithme de recherche de sous-chaîne où il est déjà décrit.

Mise en page : une animation ?

Bonjour,

la mise en page n'est pas très agréable à l’œil du fait des exemples, mais ces exemples sont utiles. Peut-être que l'on pourrait mettre en place une animation ? Voir par exemple ce qui a été fait sur Algorithme de Dijkstra. Qu'en pensez-vous ?--Roll-Morton (discuter) 3 juillet 2017 à 10:46 (CEST)