Pattern matching (KMP, Rabin-Karp) MCQs

31
Score: 0
Attempted: 0/31

1. : What is the main purpose of the Knuth-Morris-Pratt (KMP) algorithm?
(A) To sort an array
(B) To find a substring within a string
(C) To merge two sorted arrays
(D) To compute the longest common subsequence

2. : Which of the following best describes the Rabin-Karp algorithm?
(A) A linear time pattern matching algorithm
(B) A brute-force string matching algorithm
(C) A hashing-based pattern matching algorithm
(D) A divide-and-conquer algorithm

3. : What is the worst-case time complexity of the KMP algorithm?
(A) O(n)
(B) O(m)
(C) O(n + m)
(D) O(n * m)

4. : In the KMP algorithm, what does the “partial match table” help to achieve?
(A) To optimize the search time
(B) To store hash values of the pattern
(C) To keep track of the indices of matches
(D) To sort the input strings

5. : What is the main advantage of using the Rabin-Karp algorithm?
(A) Simplicity of implementation
(B) Use of a single hash function for all comparisons
(C) Constant time complexity
(D) Works better with small alphabets

6. : Which of the following is true about the Rabin-Karp algorithm?
(A) It can only match fixed-length patterns
(B) It uses rolling hash for efficiency
(C) It has no risk of hash collisions
(D) It is not suitable for large texts

7. : What is the space complexity of the KMP algorithm?
(A) O(1)
(B) O(n)
(C) O(m)
(D) O(n + m)

8. : What is a hash collision in the context of the Rabin-Karp algorithm?
(A) When two different patterns produce the same hash value
(B) When the search time increases
(C) When the algorithm fails to find a match
(D) When the input strings are too long

9. : Which of the following algorithms guarantees a worst-case linear time complexity?
(A) Brute-force string matching
(B) KMP algorithm
(C) Rabin-Karp algorithm
(D) Naive string matching

10. : How does the KMP algorithm avoid unnecessary comparisons?
(A) By hashing the pattern
(B) By using a queue
(C) By utilizing the partial match table
(D) By sorting the pattern

11. : In Rabin-Karp, how is the new hash value computed from the previous hash value?
(A) By incrementing the previous value
(B) By adding the new character’s value
(C) By using a rolling hash technique
(D) By hashing the entire substring again

12. : What is the main disadvantage of the Rabin-Karp algorithm?
(A) High space complexity
(B) Difficulty in handling long patterns
(C) Possibility of hash collisions
(D) Lack of optimization for small alphabets

13. : Which of the following is a key feature of the KMP algorithm?
(A) It only works with lowercase letters
(B) It preprocesses the pattern before searching
(C) It requires additional memory for the text
(D) It can only be used for fixed-length patterns

14. : In the context of the KMP algorithm, what does the term “backtracking” refer to?
(A) Moving back to a previous character
(B) Using previously computed information to skip unnecessary comparisons
(C) Resetting the entire search process
(D) Repeating the search for the entire text

15. : What is the time complexity of the Rabin-Karp algorithm in the average case?
(A) O(n)
(B) O(n * m)
(C) O(n + m)
(D) O(m)

16. : Which pattern matching algorithm is more efficient for multiple pattern matching?
(A) KMP
(B) Rabin-Karp
(C) Naive string matching
(D) Boyer-Moore

17. : What type of algorithm is KMP classified as?
(A) Brute force
(B) Greedy
(C) Dynamic programming
(D) String matching

18. : What is the length of the partial match table in KMP?
(A) Equal to the length of the text
(B) Equal to the length of the pattern
(C) Twice the length of the pattern
(D) Variable depending on input

19. : Which of the following statements is true regarding the rolling hash in Rabin-Karp?
(A) It calculates a hash value from scratch each time
(B) It allows quick re-calculation of hash values for overlapping substrings
(C) It is not suitable for dynamic patterns
(D) It requires additional libraries to implement

20. : In KMP, when a mismatch occurs after some matches, what does the algorithm utilize?
(A) A new search
(B) The length of the longest prefix which is also a suffix
(C) A different pattern
(D) A random character

21. : What is the primary goal of pattern matching algorithms?
(A) To sort data
(B) To find occurrences of a substring within a larger string
(C) To manipulate string data
(D) To encode data efficiently

22. : Which algorithm would likely perform better on very large texts with many potential matches?
(A) KMP
(B) Rabin-Karp
(C) Naive search
(D) Boyer-Moore

23. : How is the hash function chosen in the Rabin-Karp algorithm?
(A) It must be a prime number
(B) It can be any arbitrary function
(C) It is predefined in the algorithm
(D) It is a constant value

24. : What happens if a hash collision occurs in Rabin-Karp?
(A) The algorithm stops
(B) The algorithm re-calculates the hash
(C) The algorithm verifies characters to check for a match
(D) The hash value is discarded

25. : In the KMP algorithm, how are the values in the partial match table calculated?
(A) Randomly
(B) Based on the text
(C) From the pattern itself
(D) By a brute-force comparison

26. : What does the term “substring” refer to in string algorithms?
(A) A larger string containing another
(B) A sequence of characters within a string
(C) A fixed-length segment of memory
(D) A collection of characters

27. : Which of the following is a benefit of using KMP over brute-force methods?
(A) It requires less memory
(B) It avoids unnecessary comparisons
(C) It is simpler to understand
(D) It can only be used for fixed-length patterns

28. : How does Rabin-Karp handle varying pattern lengths?
(A) It only works for fixed lengths
(B) It computes different hash functions
(C) It adjusts the hash value dynamically
(D) It cannot handle varying lengths

29. : What is the primary drawback of KMP in practical applications?
(A) High space complexity
(B) Slow performance on small texts
(C) Complexity of implementation
(D) Inefficiency in multiple pattern searches

30. : Which of the following scenarios is most suitable for the Rabin-Karp algorithm?
(A) Searching for a single short pattern
(B) Searching for multiple patterns simultaneously
(C) Sorting a list of strings
(D) Reversing a string

31. : What is the typical use case for the KMP algorithm?
(A) Sorting data
(B) Searching for a single substring in a long text
(C) Encrypting data
(D) Compressing strings

Data Structures MCQs

Basic Concepts

Linear Data Structures MCQs

Non-Linear Data Structures MCQs

Hashing MCQs MCQs

Hash Tables

Sorting and Searching Algorithms MCQs

Miscellaneous

Pattern matching (KMP, Rabin-Karp) MCQs
By: Prof. Dr. Fazal Rehman | Last updated: May 14, 2025

Related Posts: