Exercises

1. The Rabin-Karp algorithm can be used very effectively for 2-dimensional pattern matching- finding whether a ``pattern'' array of characters appears as a subarray of a ``text'' array of characters.

   Show how the algorithm could be changed for the two-dimensional case, and generalize your algorithm to work with higher numbers of dimensions.

2. Find at least one other hashing function that can be used with the Rabin-Karp string matching algorithm. Try to find one that is efficient to compute.
3. Modify the stringSearchRK function so that it randomly selects a new prime m whenever the number of mismatches exceeds 4/m of the total number of characters processed at any point in the text. You may assume the existence of an array of suitable primes.
4. What is the maximum number of times that any character in the text will be looked at by the stringSearchKMP function? Is it possible that adjacent characters in the text will be considered this many times?
5. The way that the skipArray is computed for the Knuth-Morris-Pratt string searching algorithm is quite inefficient. This means that searching for relatively long patterns in relatively short texts is inefficient with this function, because the time necessary to compute the skipArray is comparable to the time necessary to perform the search itself!

   Show how the computation of the skipArray can be significantly improved. (It can be done in time O(M).) This is not an easy problem.