# String Matching Algorithm MCQ

1. What is a Rabin and Karp Algorithm?

a) String Matching Algorithm

b) Shortest Path Algorithm

c) Minimum spanning tree Algorithm

d) Approximation Algorithm

Answer: a

The string matching algorithm which was proposed by Rabin and Karp generalizes to other algorithms and for two-dimensional pattern matching problems.

2. What is the pre-processing time of the Rabin and Karp Algorithm?

a) Theta(m^{2})

b) Theta(mlogn)

c) Theta(m)

d) Big-Oh(n)

Answer: c

The for loop in the pre-processing algorithm runs for m (length of the pattern) times. Hence the pre-processing time is Theta(m).

3. Rabin Karp’s Algorithm makes use of elementary number theoretic notions.

a) True

b) False

Answer: a

Rabin Karp’s Algorithm makes use of elementary theoretic number notions such as the equivalence of two numbers modulo a third number.

4. What is the basic formula applied in Rabin Karp Algorithm to get the computation time as Theta(m)?

a) Halving rule

b) Horner’s rule

c) Summation lemma

d) Cancellation lemma

Answer: b

The pattern can be evaluated in time Theta(m) using Horner’s rule to find Rabin Karp Algorithm equation

p = P[m] + 10(P[m-1] + 10(P[m-2] +…+ 10(P[2]+10P[1])…)).

5. What is the worst-case running time of the Rabin Karp Algorithm?

a) Theta(n)

b) Theta(n-m)

c) Theta((n-m+1)m)

d) Theta(nlogm)

Answer: c

The worst-case running time of the Rabin Karp Algorithm is Theta(n-m+1)m). We write Theta(n-m+1) instead of Theta(n-m) because there are n-m+1 different values that the given text takes on.

6. Rabin- Karp algorithm can be used for discovering plagiarism in a sentence.

a) True

b) False

Answer: a

Since the Rabin-Karp algorithm is a pattern detecting algorithm in a text or string, it can be used for detecting plagiarism in a sentence.

9. What happens when the modulo value(q) is taken large?

a) Complexity increases

b) Spurious hits occur frequently

c) Cost of extra checking is low

d) Matching time increases

Answer: c

If the modulo value(q) is large enough then the spurious hits occur infrequently enough that the cost of extra checking is low.

10. Given a pattern of the length-5 window, find the suitable modulo value.

a) 13

b) 14

c) 12

d) 11

Answer: a

The modulus q is typically chosen as a prime number that is large enough to reduce the complexity when p is very large.

11. 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

a) 11-16

b) 3-8

c) 13-18

d) 15-20

Answer: c

The pattern 2 1 9 3 6 occurs in the text starting from positions 13 to 18. In the given pattern value is computed as 12 by having the modulus as 21. The same text string values are computed for each possible position of a 5-length window.

12. 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

a) 6-10

b) 12-16

c) 3-7

d) 13-17

Answer: d

The sub-string in the range 13-17, 6 7 3 9 9 produces the same value 7 as the given pattern. But the pattern numbers don’t match with the substring identified, hence it is a spurious hit.

13. If the expected number of valid shifts is small and the modulus is larger than the length of the pattern what is the matching time of the Rabin Karp Algorithm?

a) Theta(m)

b) Big-Oh(n+m)

c) Theta(n-m)

d) Big-Oh(n)

Answer: b

When the number of valid shifts(v) is Big-Oh(1) and q>=m then the matching time is given by O(n)+O(m(v+n/q)) and is simplified as Big-Oh(n+m)

14. What is the basic principle in the Rabin Karp algorithm?

a) Hashing

b) Sorting

c) Augmenting

d) Dynamic Programming

Answer: a

The basic principle employed in the Rabin Karp algorithm is hashing. In the given text every substring is converted to a hash value and compared with the hash value of the pattern.

15. Who created the Rabin Karp Algorithm?

a) Joseph Rabin and Michael Karp

b) Michael Rabin and Joseph Karp

c) Richard Karp and Michael Rabin

d) Michael Karp and Richard Rabin

Answer: c

Rabin Karp algorithm was invented by Richard Karp and Michael Rabin in the year 1987 for searching a pattern in a given string.

1. Which of the following is the fastest algorithm in the string matching field?

a) Boyer-Moore’s algorithm

b) String matching algorithm

c) Quick search algorithm

d) Linear search algorithm

Answer: c

The quick search algorithm is the fastest algorithm in the string matching field whereas the Linear search algorithm searches for an element in an array of elements.

2. Which of the following algorithms formed the basis for the Quick search algorithm?

a) Boyer-Moore’s algorithm

b) Parallel string matching algorithm

c) Binary Search algorithm

d) Linear Search algorithm

Answer: a

The quick search algorithm was originally formed to overcome the drawbacks of Boyer-Moore’s algorithm and also for increased speed and efficiency.

3. What is the time complexity of the Quick search algorithm?

a) O(n)

b) O(log n)

c) O(m+n)

d) O(mn)

Answer: c

The time complexity of the Quick search algorithm was found to be O(m+n) and is proved to be faster than Boyer-Moore’s algorithm.

4. What character shift tables do the quick search algorithm use?

a) good-character shift tables

b) bad-character shift tables

c) next-character shift tables

d) both good and bad characters shift tables

Answer: b

The quick search algorithm uses only bad character shift tables and it is one of the reasons for its increased speed than Boyer-Moore’s algorithm.

5. What is the space complexity of the quick search algorithm?

a) O(n)

b) O(log n)

c) O(m+n)

d) O(mn)

Answer: a

The space complexity of the quick search algorithm is mathematically found to be O(n) where n represents the input size.

6. Quick search algorithm starts searching from the left-most character to the left.

a) true

b) false

Answer: a

The quick search algorithm starts searching from the leftmost character to the right and it uses only bad character shift tables.

7. What character shift tables do Boyer-Moore’s search algorithm use?

a) good-character shift tables

b) bad-character shift tables

c) next-character shift tables

d) both good and bad characters shift tables

Answer: d

Boyer-Moore’s search algorithm uses both good and bad character shift tables whereas the quick search algorithm uses only bad character shift tables.

8. What is the worst-case running time in the searching phase of Boyer-Moore’s algorithm?

a) O(n)

b) O(log n)

c) O(m+n)

d) O(mn)

Answer: d

If the pattern occurs in the text, the worst-case running time of Boyer-Moore’s algorithm is found to be O(mn).

9. The searching phase in the quick search algorithm has good practical behaviour.

a) true

b) false

Answer: a

During the searching phase, the comparison between pattern and text characters can be done in any order. It has a quadratic worst-case behaviour and good practical behaviour.

10. Given input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the first index of the pattern match using a quick search algorithm.

a) 2

b) 6

c) 11

d) 14

Answer: b

By using a quick search algorithm, the given input text string is preprocessed and starts its search from the left-most character and finds the first occurrence of the pattern at index=2.