मैं दो बहुत बड़ी तार है और मैं उनके Longest Common Substring पता लगाने के लिए कोशिश कर रहा हूँ।सबसे लंबे समय तक सामान्य सबस्ट्रिंग की लंबाई की गणना कैसे करें?
एक तरह से प्रत्यय पेड़ (एक बहुत अच्छा जटिलता है माना जाता है, हालांकि एक जटिल कार्यान्वयन) का उपयोग किया जाता है, और एक अन्य गतिशील प्रोग्रामिंग विधि (दोनों ऊपर लिंक विकिपीडिया पृष्ठ पर उल्लेख कर रहे हैं) है।
गतिशील प्रोग्रामिंग
समस्या गतिशील प्रोग्रामिंग विधि एक विशाल चल रहा समय है कि (जटिलता O(n*m)
, जहां n
और m
दो तार की लंबाई हो रहा है) का उपयोग करना।
क्या मैं (प्रत्यय के पेड़ को लागू करने के कूदने से पहले) जानना चाहता हूँ: यह एल्गोरिथ्म तेजी लाने के लिए अगर मैं केवल आम-स्ट्रिंग की लंबाई पता करने के लिए (और नहीं आम-स्ट्रिंग ही) चाहते हैं संभव है?
@Billy ONeal: आप प्रत्यय पेड़ और गतिशील प्रोग्रामिंग तुलना कर रहे हैं? मैं इसके लिए नहीं पूछ रहा हूँ।'मुझे क्या पता होना चाहिए कि क्या गतिशील प्रोग्रामिंग एल्गोरिदम तेजी से बनाने का कोई तरीका है यदि मैं केवल सामान्य सबस्ट्रिंग की लंबाई जानना चाहता हूं?' – Lazer
@eSKay: मेरा मानना है कि मेरे उत्तर का पहला भाग उस प्रश्न का उत्तर देता है। –
ठीक है, * मैं इसे अभ्यास में तेज़ी से कैसे बना सकता हूं? – Lazer