हमारे पास दो सेट हैं, ए और बी। इनमें से प्रत्येक सेट में तार शामिल हैं। उदाहरण: ए - {"abwcd", "dwas", "www"} और बी - {"opqr", "tops", "ibmd"} मैं सेट ए से सभी तारों में दिखाई देने वाले बाद की गणना कैसे कर सकता हूं , लेकिन सेट बी में तारों में से कोई भी नहीं? उत्तर के ऊपर उदाहरण के लिए 1 (बाद में "डब्ल्यू") है।ट्री और बाद के
यह सब एक इष्टतम तरीके से है। मैंने दो प्रयासों का उपयोग करने के बारे में सोचा, पहली बार मैंने बीई में सभी स्ट्रिंग्स के सभी चरणों को ट्राई टीबी में रखा और फिर, मैं ट्राई टी_ए में ए में सभी स्ट्रिंग्स के सभी बादों को डालने शुरू कर देता हूं, अगर त्रिभुज को अपडेट किए बिना बाद में एक ही स्ट्रिंग में पहले पाया गया था (उदाहरण: यदि मेरे पास स्ट्रिंग "एबा" है, तो मैं बाद में "ए" की गणना नहीं करता)। इस तरह, अगर मुझे ऐसा लगता है कि t_A में n (ए का आकार) उपस्थिति है, तो मैं जांचता हूं कि यह t_B में है, और यदि ऐसा नहीं है, तो मैं इसे गिनता हूं। लेकिन यह बहुत धीमा है, अगर ए और बी के आकार 15 है और तार लगभग 100 वर्ण लंबे हैं, तो मेरे कार्यक्रम 1 सेकंड से अधिक समय तक चलते हैं।
संपादित करें: के बाद से किसी भी subsqeunce स्ट्रिंग के अंतिम वर्ण में या इसे करने से पहले एक चरित्र में समाप्त होता है, हम सब subsequences, लेकिन जो कि स्ट्रिंग के अंतिम वर्ण में खत्म हो generat की जरूरत नहीं है। जब मैं उन्हें त्रिभुज में धक्का देता हूं, तो मैं प्रत्येक नोड को 1 के साथ नोट करता हूं। इसलिए यदि मेरे पास "abcd" स्ट्रिंग है, तो मैं केवल "abcd", "bcd", "cd" और "d" दबाता हूं, क्योंकि यह ' त्रिभुज का कंकाल '। लेकिन यह एक बहुत बड़ा अनुकूलन नहीं है, मैं अभी भी कुछ बेहतर खोज रहा हूं।
मुझे आश्चर्य नहीं है कि आपका समाधान कुछ हद तक धीमा है, आपके द्वारा वर्णित एल्गोरिदम में n^2 के क्रम में रन-टाइम है। इन तरह की समस्याओं के साथ अक्सर, गतिशील प्रोग्रामिंग एक अच्छा दृष्टिकोण है। लेकिन बाद की समस्याएं एल्गोरिदमिक दृष्टिकोण से कुख्यात रूप से कठिन हैं, इसलिए n^2 शायद सबसे अच्छा हो सकता है जिसके लिए आप उम्मीद कर सकते हैं। – pg1989
हाँ, एन^2 सबसे अच्छा है जिसके साथ मैं आ सकता हूं, फिर मैंने एक अनुकूलन के बारे में सोचा, क्योंकि किसी भी subsqeunce स्ट्रिंग के अंतिम चरित्र में या उसके पहले एक चरित्र में समाप्त होता है, इसलिए अब मैं सभी अनुक्रमों को उत्पन्न नहीं कर रहा हूं , लेकिन जो स्ट्रिंग के आखिरी चरित्र में समाप्त होते हैं, और जब मैं उन्हें त्रिभुज में धक्का देता हूं, तो मुझे लगता है कि प्रत्येक नोड 1 के साथ नया है, या अगर यह पहले से ही था तो इसे बढ़ाएं। तो अगर मेरे पास "abcd" स्ट्रिंग है, तो मैं केवल "abcd", "bcd", "cd" और "d" दबाता हूं, क्योंकि यह त्रिभुज का 'कंकाल' होना चाहिए। लेकिन यह एक बहुत बड़ा अनुकूलन नहीं है, मैं अभी भी कुछ बेहतर खोज रहा हूं। –
मुझे लगता है कि बाद में उन सबस्ट्रिंग्स को कॉल करना बेहतर होगा। उपक्रम केवल एक शब्द है जो हमारे पास एक अनुक्रम के लिए है जिसे शेष तत्वों के क्रम को बदले बिना कुछ तत्वों को हटाकर किसी अन्य अनुक्रम से प्राप्त किया जा सकता है। –