Exercise

1. Show the KMP prefix function for the pattern "aabaabcab".
2. If the expected number of valid shifts is small and the modulus is larger than the length of the pattern, then what is the matching time of the Rabin-Karp algorithm?
   1. Theta (m)
   2. Big O (n+m)
   3. Theta (n-m)
   4. Big O (n)
3. How many spurious hits does the Rabin-Karp string matching algorithm encounter in the text T = "3141512653849792" when looking for all occurrences of the pattern P = "26", working modulo q = 11, and over the alphabet set Σ = {0, 1, 2,..., 9}?
4. What is the basic formula applied in the Rabin-Karp algorithm to get the computation time as Theta (m)?
   1. Halving rule
   2. Horner’s rule
   3. Summation lemma
   4. Cancellation lemma
5. The Rabin-Karp algorithm can be used for discovering plagiarism in text documents.
   1. True
   2. False
   ...