Question:
What is the time complexity of searching for a pattern of length \(m\) in a text of length \(n\) using the Knuth-Morris-Pratt (KMP) string matching algorithm?
Knuth-Morris-Pratt (KMP) स्ट्रिंग मिलान कलनविधि का उपयोग करके \(n\) लंबाई के टेक्स्ट में \(m\) लंबाई के पैटर्न को खोजने की समय जटिलता क्या है?
Options:
- \(O(n + m)\)
- \(O(n \times m)\)
- \(O(n \log m)\)
- \(O(m^2)\)
- \(O(n + m)\)
- \(O(n \times m)\)
- \(O(n \log m)\)
- \(O(m^2)\)
Correct Answer: a)
Explanation:
The KMP algorithm precomputes the Longest Proper Prefix which is also a Suffix (LPS) array in \(O(m)\) time, and then scans the text in \(O(n)\) time without backtracking the text pointer, achieving linear \(O(n + m)\) time.
KMP एल्गोरिदम पहले LPS तालिका \(O(m)\) में बनाता है और फिर बिना बैकट्रैकिंग के टेक्स्ट को \(O(n)\) में स्कैन करता है, कुल समय \(O(n+m)\) होता है।