Algorithm MCQs

1. What is the worst-case time complexity of the KMP algorithm?

a)O(n^2) b)O(mn) c)O(n + m) d)O(nlog m)

2. What is the purpose of the prefix function Pi in the KMP algorithm?

a) To compute the hash value of the pattern b) To avoid backtracking on the text c) To sort the characters of the pattern d) To divide the text into smaller substrings

3. Which of the following is true about the KMP algorithm?

a) It requires backtracking on the text. b) It has a preprocessing step that takes O(m) time. c) It cannot handle patterns with repeated characters. d) It uses a rolling hash function to compare substrings.

4. What is the time complexity of the KMP algorithm's matching phase?

a)O(n) b)O(m) c)O(n + m) d)O(nlog m)

5. Which of the following is a key advantage of the KMP algorithm over the Naive Algorithm?

a) It has a lower worst-case time complexity. b) It uses less memory. c) It can handle patterns with repeated characters. d) It has better average-case performance.

6. What is the role of the prefix function Pi in the KMP algorithm?

a) To compute the hash value of the pattern b) To determine the longest prefix of the pattern that is also a suffix of the current substring c) To sort the characters of the pattern d) To divide the text into smaller substrings

7. What is the time complexity of computing the prefix function Pi in the KMP algorithm?

a)O(n) b)O(m) c)O(n + m) d)O(nlog m)

8. Which of the following is true about the KMP algorithm?

a) It requires backtracking on the text. b) It has a preprocessing step that takes O(m) time. c) It cannot handle patterns with repeated characters. d) It uses a rolling hash function to compare substrings.

9. What is the purpose of the prefix function Pi in the KMP algorithm?

a) To compute the hash value of the pattern b) To avoid backtracking on the text by using information from previous matches c) To sort the characters of the pattern d) To divide the text into smaller substrings

10. What is the key idea behind the KMP algorithm?

a) It uses a rolling hash function to compare substrings. b) It avoids backtracking on the text by using a prefix function. c) It sorts the characters of the pattern before matching. d) It divides the text into smaller substrings for parallel processing.

11. What is the worst-case time complexity of the Naive String Matching algorithm?

a)O(n) b)O(m) c)O((n-m+1)m) d)O(nlog m)

12. Which algorithm uses a rolling hash function to improve the average-case performance of string matching?

a) Naive Algorithm b) Rabin-Karp Algorithm c) Knuth-Morris-Pratt Algorithm d) Boyer-Moore Algorithm

13. What is the worst-case time complexity of the Knuth-Morris-Pratt (KMP) algorithm?

a)O(n) b)O(m) c)O(n + m) d)O(nlog m)

14. What is the purpose of the prefix function Pi in the KMP algorithm?

a) To compute the hash value of the pattern b) To avoid unnecessary comparisons by using information from previous matches c) To sort the characters of the pattern d) To divide the text into smaller substrings

15. Which of the following is true about the Rabin-Karp Algorithm?

a) It always performs better than the KMP algorithm. b) It has a preprocessing step that takes O(m) time. c) It cannot handle patterns with repeated characters. d) It uses a rolling hash function to compare substrings.

16. What is the time complexity of the KMP algorithm's matching phase?

a)O(n) b)O(m) c)O(n + m) d)O(nlog m)

17. Which of the following is a key advantage of the Rabin-Karp Algorithm over the Naive Algorithm?

a) It has a lower worst-case time complexity. b) It uses less memory. c) It can handle patterns with repeated characters. d) It has better average-case performance.

18. What is the purpose of the prefix functionPi in the KMP algorithm?

a) To compute the hash value of the pattern b) To avoid backtracking on the text by using information from previous matches c) To sort the characters of the pattern d) To divide the text into smaller substrings

19. What is the key idea behind the KMP algorithm?

a) It uses a rolling hash function to compare substrings. b) It avoids backtracking on the text by using a prefix function. c) It sorts the characters of the pattern before matching. d) It divides the text into smaller substrings for parallel processing.

20. What is the time complexity of the KMP algorithm's preprocessing phase?

a)O(n) b)O(m) c)O(n + m) d)O(nlog m)

Knuth-Morris-Pratt (KMP) Algorithm MCQs

Your Score: /20