What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?

M

Mr. Dubey

🎓 Coach ⭐ 103.11K Points

📊 Design and Analysis of Algorithms

Q. What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?

(A) o(n + m)
(B) o(m)
(C) o(n)
(D) o(m * n)

💬 Discuss

✅ Correct Answer: (B) o(m)

Explanation: z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it an auxiliary space of o(m) for maintaining z array.

Explanation by: Mr. Dubey

z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it an auxiliary space of o(m) for maintaining z array.

💬 Discussion

📊 Question Analytics

👁️

723

Total Visits

📽️

2 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

96%

Success Rate