Virtual Labs

1. What is the time complexity of the KMP Algorithm? (M = length of pattern, N = length of string in which pattern is searched)

a: O(M×N) Explanation

Explanation

b: O(M^N) Explanation

Explanation

c: O(M+N) Explanation

Explanation

d: None of these Explanation

Explanation

2. Given the pattern to be found, which of the following is the correct LPS array?
Pattern = AABAAC

a: 1 0 1 2 0 0 Explanation

Explanation

b: 0 0 1 0 1 2 Explanation

Explanation

c: 0 1 0 1 2 0 Explanation

Explanation

d: 0 1 0 2 2 0 Explanation

Explanation

3. Given Input String and Pattern, find the first index of the input string that matches the pattern using the KMP algorithm.
Input String = "TSATLEADSAT"
Pattern = "SAT"

a: 8 Explanation

Explanation

b: 10 Explanation

Explanation

c: 1 Explanation

Explanation

d: 3 Explanation

Explanation

4. What is the main advantage of the KMP algorithm over the naive string matching algorithm?

a: It uses less memory Explanation

Explanation

b: It never re-examines text characters that have already been matched Explanation

Explanation

c: It works only with ASCII characters Explanation

Explanation

d: It requires the pattern to be sorted Explanation

Explanation

5. In the LPS array construction, what does LPS[i] represent?

a: The total number of characters in the pattern up to index i Explanation

Explanation

b: The length of the longest proper prefix which is also a suffix for the substring pattern[0...i] Explanation

Explanation

c: The number of times character at index i appears in the pattern Explanation

Explanation

d: The position where the pattern matching should restart after a mismatch Explanation

Explanation