ओ (एन) समय के तहत हम "सबस्ट्रिंग-मैच" कैसे प्राप्त करते हैं?

Question

मेरे पास एक असाइनमेंट है जिसके लिए यादृच्छिक इनपुट की एक बड़ी फ़ाइल पढ़ने की आवश्यकता है, उदाहरण के लिए:

Adana 
Izmir Adnan Menderes Apt 
Addis Ababa 
Aden 
ADIYAMAN 
ALDAN 
Amman Marka Intl Airport 
Adak Island 
Adelaide Airport 
ANURADHAPURA 
Kodiak Apt 
DALLAS/ADDISON 
Ardabil 
ANDREWS AFB 
etc.. 

अगर मैं एक खोज शब्द निर्दिष्ट करता हूं, तो प्रोग्राम को उन रेखाओं को ढूंढना होता है जहां एक सबस्ट्रिंग होता है। उदाहरण के लिए, यदि खोज शब्द "उरधा" है, तो प्रोग्राम ANURADHAPURA दिखाना चाहिए। यदि खोज शब्द "हवाईअड्डा" है, तो प्रोग्राम को Amman Marka Intl Airport, Adelaide Airport

असाइनमेंट चश्मे से उद्धरण दिखाया जाना चाहिए: "आप इस एप्लिकेशन को दक्षता लेते हुए प्रोग्राम करना चाहते हैं, हालांकि बड़ी मात्रा में डेटा और प्रोसेसिंग शामिल है .. "

मैं लूप का उपयोग करके आसानी से इस कार्यक्षमता को प्राप्त कर सकता हूं लेकिन प्रदर्शन ओ (एन) होगा। मैं trie का उपयोग करने के बारे में सोच रहा था, लेकिन यह केवल तभी काम करता है जब सबस्ट्रिंग इंडेक्स 0 से शुरू होता है। Xzx39

मैं सोच रहा था कि कौन से समाधान हैं जो ओ (एन) से बेहतर प्रदर्शन प्रदान करते हैं?

Answer 1

आप Boyer-Moore string search algorithm या Knuth-Morris-Pratt string search algorithm पर एक नज़र डाल सकते हैं। उनके पास अच्छा एसिम्प्टोटिक प्रदर्शन है, लेकिन मुझे एल्गोरिदम के बारे में पता नहीं है जिसे कम से कम एक बार (लगभग सभी) इनपुट और आउटपुट स्ट्रिंग दोनों को पढ़ने की आवश्यकता नहीं होगी, और इस प्रकार ओ (एन) प्रदर्शन से बेहतर होगा (जहां n इनपुट का आकार है)।

Answer 2

Here's ओ (एन) के साथ सबसे बुरी स्थिति समय जटिलता के रूप में। http://www-igm.univ-mlv.fr/~lecroq/string/

Answer 3

मेरे पेट कहते हैं कि आप एक Trie की सही रास्ते सोच पर कर रहे हैं और आपको लगता है कि Suffix Tree के लिए लिंक Wikipedia पर trie पृष्ठ के इस अनुभाग की जांच करना चाहते हो सकता है:

वैसे, अगर आप इस लिंक को बुकमार्क करना चाहिए कुछ और विचारों के लिए। हे (एन) विचार दुर्भाग्य से।

Answer 4

यह इनपुट पाठ लगभग स्थिर सामग्री (या मान नहीं जोड़े जाते हैं तो अक्सर, और मूल्यों इनपुट स्रोत के अंत में जोड़ा जाता है) है, लेकिन खोज अक्सर है आप निम्नलिखित की कोशिश कर सकते हैं (शायद trie के रूप में ही)

1) आप सभी पाठ() है और यह भी तो नए तत्व जोड़ दिया जाता है अद्यतन और अनुक्रमित तालिका (प्रतीक का मानचित्र तैयार समन्वय करने के लिए (लाइन या स्थिति के साथ लाइन) पढ़ेंगे जहां मिलान होता है)

'aa' - 1, 15, 27... 
'as' - 1, 15, 17... 
'ba' - 2, 3, 15... 
... 

2) इंडेक्स तालिका में पहले 2 प्रतीकों द्वारा पहली खोज समन्वय

3) फिर

Answer 5

बॉयर-मूर और कई एल्गोरिदम जो इसके कुछ विचारों पर भिन्नताओं का उपयोग करते हैं, इनपुट इनपुट में खोज जारी रखें "ओ (एन/एम)" (जहां एन घास की लंबाई है और मी सुई की लंबाई है) कुछ सुइयों पर सर्वोत्तम केस प्रदर्शन, लेकिन यह सुई पर गैर-पुनरावृत्ति मानदंडों पर निर्भर करता है जो मनमाने ढंग से बड़े मीटर (उदाहरण के लिए संतुष्ट करना असंभव है) चूंकि मीटर चरित्र सेट आकार से बहुत बड़ा हो जाता है), ओ (एन/256) और इस प्रकार ओ (एन) जैसे कुछ बेहतरीन मामलों को भी बनाते हैं। अभी भी असली दुनिया के अनुप्रयोगों में जहां मी छोटा होता है और सुइयों रोगजनक रूप से आवधिक नहीं होते हैं, बीएम और उसके चचेरे भाई बहुत अच्छी तरह से प्रदर्शन कर सकते हैं।

व्यक्तिगत रूप से मैं "दो मार्ग" एल्गोरिदम (ग्लिब कार्यान्वयन में उपयोग किए जाने वाले बीएम-जैसे एक्सटेंशन के साथ) की सिफारिश करता हूं, इस तथ्य के लिए कि उसने ओ (एन) सीमाओं और निरंतर कार्यस्थल की गारंटी दी है।