Algorytm Karpa-Rabina

Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca – służy do lokalizowania w tekście określonego podciągu. Został stworzony w 1987 roku przez Michaela O. Rabina i Richarda Karpa. Dany jest wzorzec (złożony z znaków) oraz przeszukiwany ciąg (złożony z znaków; ). Problem dopasowania wzorca polega na znalezieniu takiego indeksu dla którego W algorytmie Karpa-Rabina wykorzystuje się funkcję mieszającą Przeglądane są wszystkie podciągi dla ale bezpośrednie porównania podciągu z (które jest bardzo kosztowne) ma miejsce tylko wtedy, gdy O efektywności algorytmu decyduje konstrukcja funkcji mieszającej – powinna istnieć funkcja która niskim kosztem wyznacza na podstawie znanej już wartości W praktyce, traktuje się tekst jako liczbę zapisaną w systemie o określonej podstawie (najczęściej biorąc jako wartości cyfr kody ASCII znaków). Oczekiwana złożoność obliczeniowa jest rzędu Pseudokod (dane ): for to dobeginif thenbeginporównaj ciąg z podciągiem if wynik porównania prawdziwy then zwróć indeks endend