Computer Science and Engineering Data Structures – 2 Experiments

KMP Algorithm

1. What is the time complexity of the prepropressing function for a pattern of length M ?

a: O(M^2) Explanation

Explanation

b: O(M) Explanation

Explanation

c: O(sqrt(M)) Explanation

Explanation

d: O(M^3) Explanation

Explanation

2. What is the longest-prefix-suffix for: 'ANIDAPOPOANIDA'?

a: 6 Explanation

Explanation

b: 2 Explanation

Explanation

c: 5 Explanation

Explanation

d: 3 Explanation

Explanation