Virtual Labs

1. Which of the following is the best description of a substring?

a: A contiguous sequence of characters within a string. Explanation

Explanation

b: A sequence of characters that appear in the same order, but not necessarily contiguous. Explanation

Explanation

c: Any possible combination of the original set of characters 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: al Explanation

Explanation

d: go Explanation

Explanation

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

a: vlab Explanation

Explanation

b: labs Explanation

Explanation

c: lab Explanation

Explanation

d: None of these. Explanation

Explanation

4. Which of the following best describes the purpose of the LPS (Longest Prefix Suffix) array in the KMP algorithm?

a: It stores the length of the longest prefix which is also a suffix for each prefix of the pattern. Explanation

Explanation

b: It stores the number of pattern occurrences in the text. Explanation

Explanation

c: It stores the indices where the pattern matches the text. Explanation

Explanation

d: It stores the ASCII values of the pattern characters. Explanation

Explanation

5. What is the time complexity of the following recursive function?


          def f(n):
              if n == 0 or n == 1:
                  return 1
              return f(n-1) + f(n-2)

a: O(log n) Explanation

Explanation

b: O(n) Explanation

Explanation

c: O(2^n) Explanation

Explanation

d: O(n^2) Explanation

Explanation

6. Which of the following is NOT a valid step in the KMP preprocessing phase?

a: Initialize the LPS array to all zeros. Explanation

Explanation

b: Compare the pattern with itself to find prefixes and suffixes. Explanation

Explanation

c: Sort the pattern alphabetically. Explanation

Explanation

d: Update the LPS value when a prefix matches a suffix. Explanation

Explanation

KMP Algorithm