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) Explanation

Explanation

c: O(sqrt(M)) Explanation

Explanation

d: O(M^3) Explanation

Explanation

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

a: 6 Explanation

Explanation

b: 2 Explanation

Explanation

c: 5 Explanation

Explanation

d: 3 Explanation

Explanation

3. What is the space complexity of the LPS (Longest Prefix Suffix) array?

a: O(1) Explanation

Explanation

b: O(M) Explanation

Explanation

c: O(M^2) Explanation

Explanation

d: O(log M) Explanation

Explanation

4. During LPS array construction, what happens when we find a mismatch?

a: We restart from the beginning of the pattern Explanation

Explanation

b: We use the previously computed LPS values to avoid recomputation Explanation

Explanation

c: We skip the current character and move to the next Explanation

Explanation

d: We terminate the algorithm Explanation

Explanation

5. What does LPS[0] always equal in the LPS array?

a: 1 Explanation

Explanation

b: 0 Explanation

Explanation

c: The length of the pattern Explanation

Explanation

d: It depends on the first character Explanation

Explanation

Community Links Sakshat Portal Outreach Portal FAQ: Virtual Labs

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