Revision as of 10:59, 28 May 2004 edit Watcher (talk \| contribs) 747 edits m =Rabin-Karp and multiple pattern search= ← Previous edit		Revision as of 11:00, 28 May 2004 edit undo Watcher (talk \| contribs) 747 edits mNo edit summary Next edit →
Line 1: '''Rabin-Karp algorithm''' is a [[string searching algorithm]] that seeks a ~~patter~~pattern, i.e. a substring, within a text by using [[hashing]]. It is not widely used for single pattern matching, but is of considerable theoretical importance and is very effective for multiple pattern matching. Historically, it predates the very popular [[Knuth-Morris-Pratt algorithm]]. For text of length n and pattern of length m, its average and best case running time is proportional to n, but the worst case scenario is proportional to n*m, which is one of the reasons why it is not widely used. == Shifting substrings search and competing algorithms ==

Rabin–Karp algorithm: Difference between revisions