Revision as of 10:58, 28 May 2004 edit Watcher (talk \| contribs) 747 edits big article about Rabin-Karp string search algorithm		Revision as of 10:58, 28 May 2004 edit undo Watcher (talk \| contribs) 747 edits m =Shifting substrings search and competing algorithms= Next edit →
Line 2: == Shifting substrings search and competing algorithms == The basic problem the algorithm addresses is finding a pattern (fixed substring) of length m within a text of length n, for example "sun" in "Hello sunshine in this vale of tears." By way of comparison of the algorithms, a naive brute force string searching algorithm involves aligning the first character of the pattern with the first character of the text and checking if the pattern matches the initial substring of equivalent length. If it does not match, the pattern is shifted right by 1 and the procedure is repeated, for a worst case running time of m*n. [[Knuth-Morris-Pratt- algorithm]] is an elegant elaboration on this naive algorithm that uses precomputed data to skip forward not by 1 character, but by as many as possible for the search to succeed. == Use of hashing for shifting substring search ==

Rabin–Karp algorithm: Difference between revisions