Algoritmo di Rabin-Karp

L'algoritmo di Rabin–Karp è un algoritmo di pattern matching su stringhe proposto da Michael O. Rabin e Richard M. Karp nel 1987. Utilizza una funzione di hash per individuare possibili occorrenze del pattern, e per la ricerca di un pattern di lunghezza in un testo di lunghezza ha una complessità computazionale al caso medio di in tempo e di in spazio, e di in tempo al caso pessimo. L'algoritmo può essere generalizzato per la ricerca simultanea di pattern multipli nello stesso testo. Nella ricerca di un singolo pattern è efficiente in pratica, ma ha una complessità al caso pessimo superiore ad altri algoritmi come quelli di Knut-Morris-Pratt, e Boyer-Moore.