Content deleted Content added
rm personal site per WP:ELNO |
No edit summary Tag: Reverted |
||
Line 13:
}}
In [[computer science]], the '''Rabin–Karp algorithm''' or '''Karp–Rabin algorithm''' is a [[string-searching algorithm]] created by {{harvs|first1=Richard M.|last1=Karp|author1-link=Richard M. Karp|first2=Michael O.|last2=Rabin|author2-link=Michael O. Rabin|year=1987|txt}} that uses [[Hash function|hashing]] to find an exact match of a pattern string in a text. It uses a [[rolling hash]] to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. Generalizations of the same idea can be used to find more than one match of a single pattern, or to find matches for more than one pattern.
This algorithm doesn't work.
To find a single match of a single pattern, the [[expected time]] of the algorithm is [[linear time|linear]] in the combined length of the pattern and text,
| |||