String Algorithms: KMP, Rabin-Karp, Z-Algorithm Quiz Quiz

Challenge your knowledge of classical string search algorithms with focused questions on the KMP algorithm, Rabin-Karp hashing, and the Z-algorithm. This quiz helps solidify your understanding of key concepts, practical techniques, and subtle distinctions involved in efficient string pattern search methods.

1. Failure Function in KMP

   Which of the following best describes the main purpose of the failure (prefix) function used in the Knuth-Morris-Pratt (KMP) algorithm during pattern searching?

   1. To determine how much to shift the pattern when a mismatch occurs
   2. To find all occurrences using rolling hashes
   3. To preprocess the text for faster matching
   4. To calculate the hash value of the pattern

   Explanation: The failure function in KMP helps determine where to resume the pattern search in case of a mismatch, avoiding unnecessary re-checks. It does not calculate hashes (which is a Rabin-Karp concept), nor does it use rolling hashes to find matches. Preprocessing the text is not required by KMP—the function only preprocesses the pattern.

2. Rabin-Karp Hash Collisions

   In the Rabin-Karp algorithm, what is the key risk associated with using hash values to compare substrings in the text to the pattern?

   1. The algorithm cannot handle numeric patterns
   2. It requires quadratic time for all cases
   3. The pattern must be longer than the text
   4. Hash collisions can cause false positives

   Explanation: Hash collisions in Rabin-Karp mean two different substrings may produce the same hash value, necessitating direct string comparison after hash matches to avoid false positives. The algorithm typically has average linear time, not quadratic. The pattern can be shorter or equal to the text in regular use cases, and any sequence, including numbers, can be searched if encoded correctly.

3. Z-Algorithm Output Interpretation

   Given the string 'aabcaabxaaaz' and its Z-array, what does a value of Z[i] = 3 at some position i indicate in the context of the Z-algorithm?

   1. There are 3 patterns in the string
   2. The substring starting at i matches the prefix for 3 characters
   3. Three mismatches have occurred so far
   4. The pattern length is 3

   Explanation: A Z[i] value of 3 means that the substring starting at position i matches the prefix of the string for 3 consecutive characters. It does not indicate the number of patterns, nor does it count mismatches, or relate directly to the pattern length unless the prefix itself is exactly that long.

4. Matching Complexity Differences

   Which statement accurately compares the worst-case time complexity of searching for a pattern of length m in a text of length n using the KMP, Rabin-Karp, and Z-algorithm?

   1. KMP is always quadratic in the worst case
   2. Z-algorithm cannot be used for pattern matching
   3. Rabin-Karp always runs in O(n + m), others are slower
   4. KMP and Z-algorithm both run in O(n + m), while Rabin-Karp can degrade to O(nm)

   Explanation: Both KMP and the Z-algorithm achieve linear time O(n + m) for pattern matching, while Rabin-Karp can have O(nm) complexity if many hash collisions occur. Rabin-Karp's best average performance is linear but not always. KMP is not quadratic, and the Z-algorithm is indeed used for pattern matching.

5. Preprocessing in String Algorithms

   Which part of the input does the Z-algorithm preprocess before searching for a pattern occurrence in a given text?

   1. A concatenated string of pattern, special character, and text
   2. An array of hash values for substrings
   3. Only the text string
   4. Only the pattern string

   Explanation: The Z-algorithm constructs a new string by concatenating the pattern, a unique delimiter (like '$'), and the text to avoid overlap, then computes the Z-array for this new string. Preprocessing only the pattern or only the text is insufficient for classic pattern search using Z-algorithm. The method does not use arrays of hash values—that is typical of Rabin-Karp.