स्ट्रिंग खोज एल्गोरिदम

Question

दो स्ट्रिंग खोज एल्गोरिदम के लिए: केएमपी और प्रत्यय पेड़, जिसे किस मामले में प्राथमिकता दी जाती है? कुछ व्यावहारिक उदाहरण दें।

Answer 1

एक प्रत्यय पेड़ बेहतर है यदि आपको कई प्रश्नों का उत्तर देना होगा जैसे कि "घास में सुई मौजूद है?"। केएमपी बेहतर है अगर आपको केवल एक स्ट्रिंग को एक और स्ट्रिंग में खोजना है, और इसे कई बार नहीं करना है।

एक प्रत्यय पेड़ एक अधिक सामान्य डेटा संरचना है, इसलिए आप इसके साथ बहुत कुछ कर सकते हैं। देखें कि आप इसके साथ क्या कर सकते हैं here। केएमपी यह खोजने के लिए उपयोगी है कि कोई स्ट्रिंग किसी अन्य स्ट्रिंग में एक सबस्ट्रिंग है या नहीं।

आप अन्य एल्गोरिदम, जैसे कि Boyer-Moore, Rabin-Karp और यहां तक ​​कि बेवकूफ एल्गोरिदम भी देखना चाहते हैं, क्योंकि वहां स्थितियां (इनपुट) हैं जिनमें से एक दूसरों के मुकाबले बेहतर है।

नीचे पंक्ति है:

1. आप एक मैं उपर्युक्त तरह के प्रश्नों का एक बहुत है, तो यह एक प्रत्यय पेड़ का निर्माण और उसके बाद तेजी से प्रत्येक प्रश्न का उत्तर देने के लायक है।
2. यदि आपको उन प्रकार के प्रश्नों से अधिक करने की आवश्यकता है, तो प्रत्यय पेड़ भी भवन के लायक है।
3. यदि आप केवल कभी-कभी यह खोजते हैं कि कोई स्ट्रिंग किसी अन्य स्ट्रिंग का सबस्ट्रिंग है, तो केएमपी का उपयोग करें।