String Matching — Part 2 MCQs with Explanations

Boyer-Moore is the correct answer to “Which algorithm is well-suited for string matching when dealing with long and complex patterns”. This question is standard in competitive examination syllabi for String Matching.

It shifts the pattern to align with previously matched suffixes. is the correct answer to “In the Boyer-Moore algorithm, how is the "good suffix rule" utilized”. This question is standard in competitive examination syllabi for String Matching.

Rabin-Karp is the correct answer to “Which string matching algorithm is known for being efficient with very large alphabets”. This question is standard in competitive examination syllabi for String Matching.

It is simple to implement. is the correct answer to “What is a key characteristic of the Naive string matching algorithm”. This question is standard in competitive examination syllabi for String Matching.

Theta(m) is the correct answer to “What is the pre-processing time of Rabin and Karp Algorithm”. This question is standard in competitive examination syllabi for String Matching.

13 is the correct answer to “Given a pattern of length-5 window, find the suitable modulo value. 4 3 2 5 0”. This question is standard in competitive examination syllabi for String Matching.

Hashing is the correct answer to “What is the basic principle in Rabin Karp algorithm”. This question is standard in competitive examination syllabi for String Matching.

O(n) is the correct answer to “What is the space complexity of quick search algorithm”. This question is standard in competitive examination syllabi for String Matching.

for s=0 to n-m do if p=ts then if P[1..m]=T[s+1..s+m] then print “Pattern occurs with shift” s is the correct answer to “If n is the length of text(T) and m is the length of the pattern(P) identify the correct matching algorithm.”. This question is standard in competitive examination syllabi for String Matching.

True is the correct answer to “Rabin Karp Algorithm makes use of elementary number theoretic notions.”. This question is standard in competitive examination syllabi for String Matching.

for i=1 to m do p=(dp + P[i])mod q t0=(dt0+T[i])mod q is the correct answer to “If n is the length of text(T) and m is the length of the pattern(P) identify the correct pre-processing algorithm. (where q is a suitable modulus to reduce the complexity) p=0; t0=0;”. This question is standard in competitive examination syllabi for String Matching.

O(mn) is the correct answer to “What is the worst case running time in searching phase of Boyer-Moore's algorithm”. This question is standard in competitive examination syllabi for String Matching.

Quick search algorithm is the correct answer to “Which of the following is the fastest algorithm in string matching field”. This question is standard in competitive examination syllabi for String Matching.

Theta((n-m+1)m) is the correct answer to “What is the worst case running time of Rabin Karp Algorithm”. This question is standard in competitive examination syllabi for String Matching.

Cost of extra checking is low is the correct answer to “What happens when the modulo value(q) is taken large”. This question is standard in competitive examination syllabi for String Matching.

True is the correct answer to “Rabin- Karp algorithm can be used for discovering plagiarism in a sentence.”. This question is standard in competitive examination syllabi for String Matching.

Big-Oh(n+m) is the correct answer to “If the expected number of valid shifts is small and modulus is larger than the length of pattern what is the matching time of Rabin Karp Algorithm”. This question is standard in competitive examination syllabi for String Matching.

Boyer-Moore's algorithm is the correct answer to “Which of the following algorithms formed the basis for the Quick search algorithm”. This question is standard in competitive examination syllabi for String Matching.

13-18 is the correct answer to “Given a pattern of length- 5 window, find the valid match in the given text. Pattern: 2 1 9 3 6 Modulus: 21 Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Text: 9 2 7 2 1 8 3 0 5 7 1 2 1 2 1 9 3 6 2 3 9 7”. This question is standard in competitive examination syllabi for String Matching.

Richard Karp and Michael Rabin is the correct answer to “Who created the Rabin Karp Algorithm”. This question is standard in competitive examination syllabi for String Matching.

13-17 is the correct answer to “Given a pattern of length- 5 window, find the spurious hit in the given text string. Pattern: 3 1 4 1 5 Modulus: 13 Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Text: 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1 3 9”. This question is standard in competitive examination syllabi for String Matching.

Horner's rule is the correct answer to “What is the basic formula applied in Rabin Karp Algorithm to get the computation time as Theta(m)”. This question is standard in competitive examination syllabi for String Matching.

false is the correct answer to “Quick search algorithm starts searching from the right most character to the left.”. This question is standard in competitive examination syllabi for String Matching.

both good and bad character shift tables is the correct answer to “What character shift tables does Boyer-Moore's search algorithm use”. This question is standard in competitive examination syllabi for String Matching.

String Matching Algorithm is the correct answer to “What is a Rabin and Karp Algorithm”. This question is standard in competitive examination syllabi for String Matching.

6 is the correct answer to “Given input string = "ABCDABCATRYCARCABCSRT" and pattern string = "CAT". Find the first index of the pattern match using quick search algorithm.”. This question is standard in competitive examination syllabi for String Matching.

O(m+n) is the correct answer to “What is the time complexity of the Quick search algorithm”. This question is standard in competitive examination syllabi for String Matching.

bad-character shift tables is the correct answer to “What character shift tables does quick search algorithm use”. This question is standard in competitive examination syllabi for String Matching.

true is the correct answer to “The searching phase in quick search algorithm has good practical behaviour.”. This question is standard in competitive examination syllabi for String Matching.