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: 0 0 1 0 1 2 Explanation

Explanation

b: 0 1 0 1 2 0 Explanation

Explanation

c: 1 0 1 2 0 0 Explanation

Explanation

d: 0 1 0 1 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: 3 Explanation

Explanation

d: 1 Explanation

Explanation

4. Which of the following is a key advantage of KMP over the naive string searching algorithm?

a: KMP can search for multiple patterns at once. Explanation

Explanation

b: KMP avoids redundant comparisons by using the LPS array. Explanation

Explanation

c: KMP sorts the pattern before searching. Explanation

Explanation

d: KMP works only for numeric strings. Explanation

Explanation

5. Which of the following best describes the role of the LPS array in the KMP algorithm?

a: It helps to skip unnecessary comparisons after a mismatch. Explanation

Explanation

b: It stores the number of matches found so far. Explanation

Explanation

c: It sorts the pattern alphabetically. Explanation

Explanation

d: It counts the number of mismatches. Explanation

Explanation

6. Which of the following is NOT a valid property of the KMP algorithm?

a: It works in O(M+N) time complexity. Explanation

Explanation

b: It uses a prefix function for preprocessing. Explanation

Explanation

c: It can handle overlapping patterns efficiently. Explanation

Explanation

d: It requires the pattern to have all unique characters. Explanation

Explanation