Tools

Aim

Overview

Pretest

Naive String Searching

Aim Concept Demo Quiz

Knuth-Morris-Pratt Algorithm

Aim LPS Array Concept Demo Practice Exercise Quiz

Code Assessment

Preprocessing

Aim Concept Demo Analysis Quiz

Posttest

KMP Algorithm

Choose difficulty:

Beginner

Intermediate

Advanced

1. What is the time complexity of the preprocessing function for a pattern of length M?

a: O(M^2) Explanation

Explanation

b: O(M^3) Explanation

Explanation

c: O(M) Explanation

Explanation

d: O(sqrt(M)) Explanation

Explanation

2. What is the longest-prefix-suffix length for: 'ANIDAPOPOANIDA'?

a: 2 Explanation

Explanation

b: 3 Explanation

Explanation

c: 5 Explanation

Explanation

d: 6 Explanation

Explanation

3. Which of the following is the main purpose of the LPS array in KMP preprocessing?

a: To store the number of matches found so far. Explanation

Explanation

b: To help skip unnecessary comparisons during the search phase. Explanation

Explanation

c: To sort the pattern alphabetically. Explanation

Explanation

d: To count the number of mismatches. Explanation

Explanation

4. Which of the following is NOT a valid step in the KMP preprocessing phase?

a: Initialize the LPS array to all zeros. Explanation

Explanation

b: Compare the pattern with itself to find prefixes and suffixes. Explanation

Explanation

c: Sort the pattern alphabetically. Explanation

Explanation

d: Update the LPS value when a prefix matches a suffix. Explanation

Explanation

5. What is the space complexity of the LPS array for a pattern of length M?

a: O(M) Explanation

Explanation

b: O(1) Explanation

Explanation

c: O(M^2) Explanation

Explanation

d: O(log M) Explanation

Explanation

Community Links Sakshat Portal Outreach Portal FAQ: Virtual Labs

AGPL 3.0 & Creative Commons (CC BY-NC-SA 4.0)