On considère un "texte" (suite de caractères); on veut recherche la position dans ce texte d'un certain "motif" (autre suite de caractères). Par exemple, le motif "jour" est à recherche dans le texte "on a lu dans le journal de ce jour qu'un bandit, déjà interdit de séjour, avait commis trois agressions dans la même journée" (4 occurences). A noter que la recherche du motif " jour " (entouré d'espaces) n'aurait donné qu'une seule occurrence : "on a lu dans le journal de ce jour qu'un bandit, déjà interdit de séjour, avait commis trois agressions dans la même journée".
L'idée est de placer le motif en regard du texte et, pour une position donnée, de comparer un par un les caractères du motif aux caractères correspondants du texte ; si aucun désaccord n'est observé, on a trouvé une occurrence du motif, sinon on arrête la comparaison dès qu'un désaccord est observé et on fait glisser le motif de 1 caractère (pour ne pas risquer de rater une coïncidence) puis on recommence la comparaison.
En conséquence, si le texte comporte Lt caractères et le motif Lm caractères et si aucun caractère du motif n'est présent dans le texte on aura fait Lt - Lm comparaisons pour épuiser le texte (l'algorithme que nous allons présenter n'en aurait que (Lt - Lm)/Lm. Si les distributions de caractères sont aléatoires, la découverte d'une différence entre motif et texte n'a lieu, en moyenne, qu'après Lm/2 comparaisons, d'où une complexité de l'ordre de Lt x Lm comparaisons.
Une des idées de base de cet algorithme est de tenir compte du fait que dans la pratique la longueur du motif est considérablement plus courte que celle du texte ; on va donc réaliser un pré-traitement sur le motif : répérer, une fois pour toutes, les caractères qu'il contient et ceux qui en sont absents.
Nous allons expliquer le fonctionnement de l'algorithme par quelques exemples. Dans les figures qui suivent on a procédé aux comparaisons en commençant par la droite du motif :
Premier exemple :
Le caractère Ct ne figure pas dans le motif, toute autre comparaison avec les caractères de gauche du motif est donc inutile ; en conséquence, il faut avancer (vers la droite) le motif pour qu'il dépasse la position de Ct puis recommencer les comparaisons.
Deuxième exemple :
La première occurrence (en partant de la droite) du caractère Ct dans le motif figure à gauche du caractère Cm ; on avancera donc le motif pour mettre les deux caractère Ct en coïncidence avant de commencer une nouvelle comparaison.
Troisième exemple :
La première occurrence (en partant de la droite) du caractère Ct dans le motif figure à droite du caractère Cm, mais le désaccord a lieu pour la première occurence de Cm (dans cette comparaison), celui-ci ne figure donc pas dans la partie explorée du texte ; on avancera donc le motif pour que ce caractère Cm dépasse la position actuelle du motif.
Quatrième exemple :
Les caractères Ct et Cm figurent dans la partie droite, déjà explorée, du motif ; on a représenté la première occurrence (en partant de la droite) de chacun ; on peut donc avancer le motif pour que la plus à gauche de ces premières occurences (ici, Cm) dépasse la position actuelle du motif.
Le principe de l'algorithme va être relativement simple : pour chaque caractère de l'alphabet utilisé, on dresse la table des premières occurences (en partant de la droite) dans le motif ; on explore le motif de droite à gauche, en cas de désaccord, on détermine le déplacement en tenant compte des seuls caractères immédiatement connus : Cm et Ct.
Il faut donc définir avec précision les notations et conventions utilisées :
Il ne vous reste plus qu'à écrire l'algorithme...