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 happens when a mismatch occurs in the KMP algorithm?

a: The text pointer moves backward Explanation

Explanation

b: The pattern pointer is updated using the LPS array Explanation

Explanation

c: Both pointers are reset to the beginning Explanation

Explanation

d: The search terminates Explanation

Explanation

4. Which statement is true about the KMP algorithm's pattern pointer during a mismatch?

a: It always resets to 0 Explanation

Explanation

b: It moves to position LPS[patternIndex - 1] Explanation

Explanation

c: It moves forward by one position Explanation

Explanation

d: It stays at the same position Explanation

Explanation

5. What is the main invariant maintained by the KMP algorithm?

a: The pattern must always be shorter than the text Explanation

Explanation

b: The text pointer never backtracks Explanation

Explanation

c: All characters must match before reporting a result Explanation

Explanation

d: The pattern pointer always increases Explanation

Explanation

KMP Algorithm