ए pangrammatic window टेक्स्ट के एक बड़े टुकड़े का एक सबस्ट्रिंग है जिसमें वर्णमाला के सभी 26 अक्षर शामिल हैं। विकिपीडिया से एक उदाहरण उद्धृत करने के लिए, यह पाठ दिया गया:सबसे छोटी pangrammatic खिड़कियों को खोजने के लिए एक कुशल एल्गोरिदम?
मैंने गाया, और सोचा कि मैंने बहुत अच्छा गाया है; लेकिन उसने सिर्फ एक बहुत ही विचित्र अभिव्यक्ति के साथ अपने चेहरे पर देखा, और कहा, 'तुम कितने समय से गा रहे हो, मैडेमोइसेल?'
पाठ में सबसे छोटी pangrammatic खिड़की इस स्ट्रिंग है:
जी बहुत अच्छी तरह से; लेकिन वह सिर्फ मेरे चेहरे पर एक बहुत क्विज़िकल पूर्व
जिसमें वास्तव में कम से कम एक बार प्रत्येक पत्र होता है।
मेरा प्रश्न यह है: टेक्स्ट कॉर्पस को देखते हुए, टेक्स्ट में सबसे छोटी पेंग्रामैटिक विंडो खोजने के लिए सबसे कुशल एल्गोरिदम क्या है?
मैंने इसे कुछ विचार दिया है और पहले से ही निम्नलिखित एल्गोरिदम के साथ आया है। मुझे एक मजबूत भावना है कि ये इष्टतम नहीं हैं, लेकिन मैंने सोचा कि मैं उन्हें एक शुरुआती बिंदु के रूप में पोस्ट करूंगा।
एक सरल अनुभवहीन एल्गोरिथ्म उस समय O (n) में चलता है और अंतरिक्ष हे (1) नहीं है: स्ट्रिंग में प्रत्येक स्थान के लिए, उस स्थिति से आगे स्कैन और ट्रैक क्या पत्र देखा है (शायद थोड़ा वेक्टर में, जो, क्योंकि केवल 26 अलग-अलग अक्षर हैं, अंतरिक्ष ओ (1) लेता है)। एक बार जब आप सभी 26 अक्षरों को पा लेते हैं, तो आपके पास उस बिंदु पर शुरू होने वाली सबसे छोटी पेंग्रामैटिक विंडो की लंबाई होती है। प्रत्येक स्कैन में समय ओ (एन) लग सकता है, और ओ (एन) के कुल योग के लिए ओ (एन) स्कैन हैं।
हम एक संशोधित बाइनरी खोज का उपयोग कर समय ओ (एन लॉग एन) और स्पेस ओ (एन) में इस समस्या को भी हल कर सकते हैं। वर्णमाला के प्रत्येक अक्षर के लिए 26 सरणी बनाएं, फिर क्रमबद्ध क्रम में इनपुट टेक्स्ट में प्रत्येक अक्षर की स्थिति के साथ उन सरणी को पॉप्युलेट करें। हम पाठ को स्कैन करके बस कर सकते हैं, प्रत्येक इंडेक्स को वर्तमान चरित्र से संबंधित सरणी में जोड़ना। एक बार हमारे पास यह हो जाने के बाद, हम समय ओ (लॉग एन) में पा सकते हैं, कुछ इंडेक्स में शुरू होने वाली सबसे छोटी पेंग्रामैटिक विंडो की लंबाई, सरणी में 26 बाइनरी खोजों को चलाने से शुरुआती समय खोजने के लिए जब प्रत्येक वर्ण इनपुट सरणी में दिखाई देता है या दिए गए सूचकांक के बाद। इनमें से जो भी संख्या सबसे बड़ी है वह "लंबा ध्रुव" चरित्र देता है जो स्ट्रिंग में सबसे नीचे दिखाई देता है, और इस प्रकार पेंग्रामैटिक विंडो का अंत बिंदु देता है। इस खोज चरण को चलाने से ओ (लॉग एन) समय लगता है, और चूंकि हमें इसे स्ट्रिंग में सभी एन अक्षरों के लिए करना है, इसलिए कुल रनटाइम ओ (एन लॉग एन) है, जिसमें ओ (एन) मेमोरी उपयोग एरे के लिए है।
उपर्युक्त दृष्टिकोण के लिए एक और परिष्करण van Emde Boas trees और पूर्ववर्ती खोजों के साथ सरणी और बाइनरी खोज को प्रतिस्थापित करना है। यह निर्माण समय को ओ (एन लॉग लॉग एन) में बढ़ाता है, लेकिन O (n) स्पेस उपयोग के साथ ओ (एन लॉग लॉग एन) के नेट रनटाइम के लिए प्रत्येक खोज समय को O (लॉग लॉग n) समय में कम करता है।
क्या वहां कोई बेहतर एल्गोरिदम हैं?
मुझे यकीन है कि यह काम करता है, लेकिन मुझे यकीन नहीं है कि मैं देखता हूं कि यह किसी भी तरह से खिड़की पर गलती से क्यों नहीं छोड़ेगा। क्या आप वाकई सभी विंडोज़ पर सही ढंग से विचार करेंगे? – templatetypedef
@templatetypedef, सबूत बहुत आसान है। चरण 2 का आविष्कार यह तथ्य है कि दूसरी पुनरावर्तक से शुरू होने वाली सबसे छोटी पेंग्रामैटिक विंडो की लंबाई बिल्कुल (पहले इटरेटर - दूसरा इटरेटर) है क्योंकि पहले इटरेटर को कम करने से सेट के पात्रों में से एक को हटा दिया जाता है। तो आप इस एल्गोरिदम को अपने एन^2 एल्गोरिदम के अनुकूलित संस्करण के रूप में देख सकते हैं। –
यह ओ (एन) कैसा है, और यह वर्णमाला आकार एम पर निर्भर नहीं है? विशेष रूप से, आप चेक कैसे करते हैं "सभी 26 काउंटर शून्य होने पर रोकें।" ओ (1) में, (चूंकि यह स्थिर है, यह ओ (1) में किया जा सकता है लेकिन एम के सामान्य मामले के लिए?) – kolistivra