Q.1 Which of the following algorithms uses preprocessing of the pattern to skip unnecessary comparisons in string matching?
Naive Algorithm
Rabin-Karp
Knuth-Morris-Pratt (KMP)
Brute Force
Explanation - KMP preprocesses the pattern to build a longest prefix-suffix (LPS) table, allowing the algorithm to skip unnecessary comparisons.
Correct answer is: Knuth-Morris-Pratt (KMP)
Q.2 What is the worst-case time complexity of the naive string matching algorithm?
O(n)
O(m)
O(nm)
O(log n)
Explanation - The naive algorithm compares each substring of text with the pattern, leading to O(nm) in the worst case.
Correct answer is: O(nm)
Q.3 Rabin-Karp algorithm is efficient for multiple pattern matching because it uses:
Prefix table
Hashing
Dynamic programming
Greedy approach
Explanation - Rabin-Karp uses hashing to compare pattern and substrings efficiently, making it useful for multiple pattern matches.
Correct answer is: Hashing
Q.4 Which algorithm is best for matching multiple patterns in a text?
KMP
Naive
Aho-Corasick
Rabin-Karp
Explanation - Aho-Corasick builds a trie with failure links, enabling simultaneous pattern matching in linear time.
Correct answer is: Aho-Corasick
Q.5 In KMP, the LPS array stands for:
Longest Prefix Suffix
Longest Pattern Search
Last Prefix Shift
Longest Partial Search
Explanation - The LPS array stores the length of the longest prefix of the pattern which is also a suffix, used to skip comparisons.
Correct answer is: Longest Prefix Suffix
Q.6 What is the average-case time complexity of Rabin-Karp for single pattern matching?
O(n)
O(n+m)
O(nm)
O(log n)
Explanation - On average, Rabin-Karp achieves O(n+m) time when hash collisions are rare.
Correct answer is: O(n+m)
Q.7 Boyer-Moore algorithm improves performance by:
Using suffix trees
Using hash functions
Skipping characters with heuristics
Dynamic programming
Explanation - Boyer-Moore uses the bad-character and good-suffix heuristics to skip sections of the text.
Correct answer is: Skipping characters with heuristics
Q.8 Which heuristic in Boyer-Moore allows skipping based on mismatched characters?
Suffix heuristic
Bad-character heuristic
Prefix heuristic
LPS heuristic
Explanation - The bad-character heuristic skips text based on the position of the mismatched character in the pattern.
Correct answer is: Bad-character heuristic
Q.9 Aho-Corasick algorithm is mainly based on which data structure?
Heap
Trie
Stack
Segment Tree
Explanation - Aho-Corasick constructs a trie of patterns with failure links for efficient multi-pattern matching.
Correct answer is: Trie
Q.10 What is the best-case time complexity of the naive string matching algorithm?
O(n)
O(m)
O(nm)
O(1)
Explanation - In the best case, when mismatches occur early, the naive algorithm only requires O(n) comparisons.
Correct answer is: O(n)
Q.11 Which of the following is NOT a string matching algorithm?
KMP
Rabin-Karp
Boyer-Moore
Dijkstra
Explanation - Dijkstra’s algorithm is for shortest paths in graphs, not for string matching.
Correct answer is: Dijkstra
Q.12 Rabin-Karp algorithm suffers performance issues when:
Patterns are long
Too many hash collisions occur
Text is too small
Patterns contain only numbers
Explanation - Frequent hash collisions degrade Rabin-Karp to O(nm).
Correct answer is: Too many hash collisions occur
Q.13 What is the worst-case time complexity of KMP algorithm?
O(n+m)
O(nm)
O(log n)
O(n^2)
Explanation - KMP guarantees O(n+m) even in the worst case due to preprocessing.
Correct answer is: O(n+m)
Q.14 Suffix trees can solve string matching problems in:
O(n)
O(n+m)
O(m log n)
O(n^2)
Explanation - With suffix trees, string matching can be done in O(n+m) after construction.
Correct answer is: O(n+m)
Q.15 What is the primary drawback of suffix trees?
Hard to implement
High memory usage
Slow query time
No practical applications
Explanation - Suffix trees require significant memory overhead compared to other structures.
Correct answer is: High memory usage
Q.16 Which string matching algorithm is preferred when alphabet size is large?
Naive
KMP
Boyer-Moore
Rabin-Karp
Explanation - Boyer-Moore performs better with large alphabets due to effective heuristics.
Correct answer is: Boyer-Moore
Q.17 What is the role of failure function in KMP?
Detect hash collisions
Identify matching suffix-prefix lengths
Shift pattern randomly
Store mismatched indexes
Explanation - The failure function (LPS) helps KMP skip redundant comparisons by using prefix-suffix relationships.
Correct answer is: Identify matching suffix-prefix lengths
Q.18 Which algorithm can find all occurrences of multiple keywords simultaneously?
KMP
Aho-Corasick
Rabin-Karp
Naive
Explanation - Aho-Corasick is designed for multi-pattern searches using a trie and failure links.
Correct answer is: Aho-Corasick
Q.19 Which of the following has linear time complexity for pattern matching in all cases?
Naive
Rabin-Karp
KMP
Boyer-Moore
Explanation - KMP ensures O(n+m) in all cases, unlike others which can degrade.
Correct answer is: KMP
Q.20 Which data structure is commonly used in suffix automaton for string matching?
Linked List
State Graph
Segment Tree
Heap
Explanation - Suffix automaton uses a state graph to represent substrings and perform efficient pattern matching.
Correct answer is: State Graph
Q.21 Which string matching algorithm is best suited for DNA sequence analysis?
Naive
KMP
Suffix Tree
Boyer-Moore
Explanation - Suffix trees allow efficient searching of DNA subsequences due to large text sizes.
Correct answer is: Suffix Tree
Q.22 The Z-algorithm preprocesses the string in:
O(n)
O(nm)
O(m log n)
O(n^2)
Explanation - The Z-algorithm computes a Z-array in linear time, enabling efficient string matching.
Correct answer is: O(n)
Q.23 What is the worst-case time complexity of Boyer-Moore?
O(nm)
O(n+m)
O(n^2)
O(n)
Explanation - Though usually fast, Boyer-Moore can degrade to O(nm) in rare cases with repetitive patterns.
Correct answer is: O(nm)
Q.24 Which technique is used by Rabin-Karp to reduce recomputation of substring values?
Rolling hash
Suffix array
Trie-based matching
LPS table
Explanation - Rabin-Karp uses rolling hash to update substring hash values efficiently.
Correct answer is: Rolling hash
Q.25 The suffix array is a space-efficient alternative to:
Suffix automaton
Suffix tree
KMP
Rabin-Karp
Explanation - Suffix arrays provide similar functionality to suffix trees but with less memory usage.
Correct answer is: Suffix tree