Pattern matching (KMP, Rabin-Karp) MCQsBy: Prof. Dr. Fazal Rehman | Last updated: May 14, 2025 31 Score: 0 Attempted: 0/31 Subscribe 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 Introduction to Data Structures Abstract Data Types (ADT) MCQs Complexity Analysis MCQs Time complexity MCQs Space complexity MCQs Big O, Big Ω, Big Θ notations MCQs Linear Data Structures MCQs Arrays MCQs One-dimensional arrays MCQs Multi-dimensional arrays MCQs Operations: traversal, insertion, deletion MCQs Linked Lists MCQs Singly linked list MCQs Doubly linked list MCQs Circular linked list MCQs Stacks MCQs Stack operations (push, pop, peek) MCQs Applications of stacks (expression evaluation, recursion) MCQs Queues MCQs Queue operations (enqueue, dequeue, front, rear) MCQs Types: Simple queue, circular queue, priority queue, deque MCQs Non-Linear Data Structures MCQs Trees MCQs Binary trees MCQs Binary Search Trees (BST) MCQs AVL Trees MCQs B-trees and B+ trees MCQs Tree traversal methods (in-order, pre-order, post-order) MCQs Heaps MCQs Min-heap MCQs Max-heap MCQs Heap operations (insertion, deletion, heapify) MCQs Applications of heaps (priority queues, heap sort) MCQs Graphs MCQs Graph representation (adjacency matrix, adjacency list) MCQs Graph traversal algorithms (DFS, BFS) MCQs Shortest path algorithms (Dijkstra’s, Bellman-Ford) MCQs Minimum Spanning Tree (Kruskal’s, Prim’s) MCQs Hashing MCQs MCQs Hash Tables Hash functions MCQs Collision resolution techniques (chaining, open addressing) MCQs Applications of hashing MCQs Sorting and Searching Algorithms MCQs Sorting Algorithms MCQs Bubble sort MCQs Selection sort MCQs Insertion sort MCQs Merge sort MCQs Quick sort MCQs Heap sort MCQs Searching Algorithms MCQs Linear search MCQs Binary search MCQs Interpolation search MCQs Miscellaneous Memory Management in data structures MCQs Dynamic memory allocation MCQs Garbage collection MCQs String Manipulation Algorithms MCQs Pattern matching (KMP, Rabin-Karp) MCQs String hashing MCQs Data Structures MCQs 1 Data Structures MCQs 2 Data Structures MCQs 3 Data Structures MCQs 4 Data Structures MCQs 5 Stacks Solved MCQs Queues MCQs pointer mcqs Array MCQs Related Posts:Matching Column Quiz Test and Score code in Javascript JQuery and CSSC++ program to print pyramid pattern of numbersC++ program to print a hollow square or rectangle star patternNumber pattern program in PHPRepository Pattern in ASP.NETSofter Design pattern MCQ's