Hashing in Computer Science: Fifty Years of Slicing and Dicing

Part III: SOME NOVEL APPLICATIONS OF HASHING

CHAPTER 16

Karp-Rabin String Searching

16.1 OVERVIEW

Let y = (y₀, y₁, ···, y_n−1) be string of characters of length |y equal to n from an alphabet .

A basic string search problem P is

Given: a string x = (x₀, x₁, ···, x_m−1) of m characters from the alphabet

Determine: whether x is a substring of y = (y₀, y₁, ···, y_n−1).

When x is (resp. is not) a substring of y, we write x ⊆ y (resp. x y). In the first case, extensions of the search problem P include the following:

P1. Find the first/last occurrence of x in y; the first/last index a such that x_i = y_i+a for 0 ≤ i < m, or

P2. The set of all occurrences of x in y.

Algorithm #1 below solves P by making m bit-comparisons of x in each of the n − m possible substrings y_[i,i+m) ≡ (y_i, y_i+1, ···, y_i+m−1) for i = 0, 1, ···, n − m.

Algorithm #1: P
for i = 0 to n − m do
Set INDi = 1
for j = 0 to m − 1 do

An extensive literature including the paper by Knuth et al. [Knuth, Morris and Pratt 1977]. The performance issues include the solution’s running time (number of comparisons and arithmetic operations) and ...