On s'intéresse ici à la recherche d'un ou plusieurs mots appelés motifs dans un texte. Il est possible de considérer des généralisations où le motif est la représentation d'un ensemble fini ou même infini de mots, sous la forme d'une expression rationnelle par exemple. On suppose que le motif et le texte sont écrit sur un alphabet fixé A. Cet alphabet peut être l'ensemble des caractères ASCII ou l'ensemble {A, C, G, T} dans le cadre de la bio-informatique. On note m et n les longueurs du motif et du texte. Le motif et le texte sont alors deux suites p0...pm-1 et t0...tn-1 de symboles.
Une occurrence du motif dans le texte est une position k comprise entre 0 et n-1 telle que les symboles tk,..., tk+m-1 coïncident avec les symboles p0,...,pm-1, c'est-à-dire si tk+i = pi pour tout 0 ≤ i ≤ m-1. Le problème est de trouver toutes les occurrences du motif dans le texte. Dans la suite, on se contente de savoir trouver la première occurrence. Les autres occurrences peuvent être trouvées en continuant la recherche à partir de la position suivante.
Nous donnons ici quelques définitions qui seront utiles pour la présentation des différents algorithmes. On suppose fixé un alphabet A qui est un ensemble fini de lettres ou symboles. Un mot sur l'alphabet A est une suite finie de lettres de A. La longueur d'un mot w est le nombre de lettres de w et elle est notée |w|. Un mot est écrit par simple juxtaposition de ses lettres. Si l'alphabet est par exemple A = { a, b, c }, les mots ab, cbb et ababcb sont des mots de longueur 2, 3 et 6. La concaténation de deux mots u et v est le mot w obtenu en mettant bout à bout u et v. Ce mot w est noté uv. Si par exemple les mots u et v sont égaux à cbb et ababcb, le mot w = uv est alors égal à cbbababcb. Parmi les mots, on distingue un mot particulier de longueur 0 qui est appelé mot vide et qui est noté ε. L'ensemble de tous les mots sur A est noté A*.
Un préfixe u d'un mot w est un mot qui est un début de w, c'est-à-dire un mot u tel qu'il existe un mot v vérifiant uv = w. De manière symétrique, un suffixe v d'un mot w est une fin de w, c'est-à-dire un mot v tel qu'il existe un mot u vérifiant uv = w. Un préfixe ou suffixe de w est dit propre s'il est différent de w. Un bord d'un mot w est un mot u, différent de w, qui est à la fois préfixe et suffixe de w. Les deux seuls bords du mot abacaba sont les mots a et aba.
L'algorithme de Knuth, Morris et Pratt est une variante de l'algorithme de Morris et Pratt qui est lui même une amélioration de l'algorithme naïf. Il est assez facile de prouver que ces deux algorithmes fonctionnent en temps linéaire. L'algorithme de Boyer et Moore est souvent le plus efficace dans la pratique même s'il ne fonctionne pas en temps linéaire dans le pire des cas. L'algorithme de Aho et Corasick est une extension de l'algorithme de Knuth, Morris et Pratt pour la recherche simultanée de plusieurs motifs.
Pour (beaucoup) plus d'information sur les algorithmes de recherche de motifs, consulter la page de T. Lecroq.