KMP Algorithm

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

a: Any combination of a subset of characters from a string in the same order as the string. Explanation

Explanation

b: Contiguous sequence of characters within a string in the same order. Explanation

Explanation

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

Explanation

d: al Explanation

Explanation

Which of the following is a suffix of the string “vlabs” ?

a: vlab Explanation

Explanation

b: lab Explanation

Explanation

c: labs Explanation

Explanation

d: None of these Explanation

Explanation

Difficulty: Beginner

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

Time complexity of this program:

a: O(log n) Explanation

Explanation

b: O(n) Explanation

Explanation

c: O(n^2) Explanation

Explanation

d: O(2^n) Explanation

Explanation