Algorithme de Karp-Miller-Rosenberg
# Algorithme de Karp-Miller-Rosenberg

L'algorithme de Karp-Miller-Rosenberg est un algorithme de détection de répétitions dans une structure de données (chaînes de caractères, arbres, tableaux). Il est l'œuvre de Richard Karp, Raymond Miller et Arnold L. Rosenberg et date de 1972.

La version originelle de l'algorithme KMR est séquentielle. Sa complexité en temps est quasi linéaire en la taille de la structure en entrée. La version originelle a été dépassée par d'autres algorithmes. Cependant, l'adaptation de l'algorithme KMR en une version parallélisée est efficace. Il existe aussi une version généralisée de l'algorithme KMR qui prend plusieurs chaînes de caractères en entrée.

