Trouver toutes les occurences d'un motif dans un texte est un problème qu'on rencontre fréquemment dans les éditeurs de texte. Le plus souvent, le texte est un document en cours d’édition et le motif recherché est un mot particulier fourni par l’utilisateur. Puisqu’on a souvent recours à ce problème, on a recherché des algorithmes efficaces qui peuvent grandement améliorer la réaction de l’éditeur de texte. Ces algorithmes sont également utilisés pour trouver certains motifs dans des séquences d’ADN.

Nous allons voir la formalisation du problème et l’algorithme naïf pour la recherche d’un motif. Nous verrons ensuite l’algorithme le plus efficace en deux temps : d’abord l’idée fondamentale qui consiste à utiliser un automate fini et ensuite l’algorithme dit KMP qui construit l’automate fini à la volée.