Virtual Labs

1. Which one of the following is true in the KMP String searching algorithm? (strInd = iterator in the main string)

a: The value of strInd always increases in all iterations. Explanation

Explanation

b: The value of strInd remains the same in all the iterations. Explanation

Explanation

c: The value of strInd may or may not increase in all the iterations but it never decreases. Explanation

Explanation

d: None of the mentioned Explanation

Explanation

2. How does KMP improve the brute-force method?

a: By comparing the characters right to left instead of left to right. Explanation

Explanation

b: By searching for text in pattern instead of pattern in string Explanation

Explanation

c: By not doing redundant comparisons and using the information gained from previous comparisons Explanation

Explanation

d: All of the mentioned Explanation

Explanation

3. What is the first step in the KMP algorithm before searching for the pattern in the text?

a: Sort the pattern alphabetically. Explanation

Explanation

b: Compute the LPS (Longest Prefix Suffix) array for the pattern. Explanation

Explanation

c: Reverse the text. Explanation

Explanation

d: Count the number of pattern occurrences in the text. Explanation

Explanation

4. Which of the following is NOT a possible value in the LPS array for the pattern 'ABABAC'?

a: 0 Explanation

Explanation

b: 1 Explanation

Explanation

c: 2 Explanation

Explanation

d: 4 Explanation

Explanation

5. Which of the following best describes the worst-case time complexity of the KMP algorithm? (M = length of pattern, N = length of text)

a: O(M*N) Explanation

Explanation

b: O(M+N) Explanation

Explanation

c: O(M^N) Explanation

Explanation

d: O(N^2) Explanation

Explanation

6. Which of the following is a limitation of the KMP algorithm?

a: It cannot handle patterns with repeated characters. Explanation

Explanation

b: It requires additional space for the LPS array. Explanation

Explanation

c: It only works for numeric strings. Explanation

Explanation

d: It cannot find overlapping patterns. Explanation

Explanation

KMP Algorithm