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. Which of the following is the best description of a substring?

a: Any combination of a subset of characters from a string in the same order as the string. Explanation

Explanation

b: Contiguous sequence of characters within a string in the same order. Explanation

Explanation

c: Any possible combination of the original set of characters present in the string. Explanation

Explanation

d: None of these Explanation

Explanation

2. Which of the following is not a prefix of the string "algorithm"?

a: algo Explanation

Explanation

b: algorithm Explanation

Explanation

c: go Explanation

Explanation

d: al Explanation

Explanation

3. Which of the following is a suffix of the string "vlabs"?

a: vlab Explanation

Explanation

b: lab Explanation

Explanation

c: labs Explanation

Explanation

d: None of these Explanation

Explanation

4. In the KMP (Knuth-Morris-Pratt) algorithm, what is the purpose of the prefix table (also called LPS array)?

a: To store all possible prefixes of the pattern Explanation

Explanation

b: To avoid unnecessary comparisons by utilizing information from previous matches Explanation

Explanation

c: To count the number of characters in the pattern Explanation

Explanation

d: To reverse the pattern for backward searching Explanation

Explanation

5. What is the time complexity of the KMP string matching algorithm for searching a pattern of length m in a text of length n?

a: O(n * m) Explanation

Explanation

b: O(n + m) Explanation

Explanation

c: O(n^2) Explanation

Explanation

d: O(m^2) Explanation

Explanation

Community Links Sakshat Portal Outreach Portal FAQ: Virtual Labs

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