सबसे लंबे समय तक सामान्य सबस्ट्रिंग की लंबाई की गणना कैसे करें?

Question

मैं दो बहुत बड़ी तार है और मैं उनके Longest Common Substring पता लगाने के लिए कोशिश कर रहा हूँ।

एक तरह से प्रत्यय पेड़ (एक बहुत अच्छा जटिलता है माना जाता है, हालांकि एक जटिल कार्यान्वयन) का उपयोग किया जाता है, और एक अन्य गतिशील प्रोग्रामिंग विधि (दोनों ऊपर लिंक विकिपीडिया पृष्ठ पर उल्लेख कर रहे हैं) है।

गतिशील प्रोग्रामिंग

समस्या गतिशील प्रोग्रामिंग विधि एक विशाल चल रहा समय है कि (जटिलता O(n*m), जहां n और m दो तार की लंबाई हो रहा है) का उपयोग करना।

क्या मैं (प्रत्यय के पेड़ को लागू करने के कूदने से पहले) जानना चाहता हूँ: यह एल्गोरिथ्म तेजी लाने के लिए अगर मैं केवल आम-स्ट्रिंग की लंबाई पता करने के लिए (और नहीं आम-स्ट्रिंग ही) चाहते हैं संभव है?

Answer 1

यह व्यवहार में तेजी से हो जाएगा? हाँ। क्या यह बिग-ओह के बारे में तेज़ होगा? नहीं। गतिशील प्रोग्रामिंग समाधान हमेशा ओ (एन * एम) होता है।

समस्या यह है कि आप प्रत्यय के पेड़ के साथ हो सकती हैं कि आप अंतरिक्ष में एक विशाल दंड के लिए प्रत्यय पेड़ के रैखिक समय स्कैन व्यापार है। प्रत्यय पेड़ आम तौर पर उस तालिका से काफी बड़े होते हैं जिसे आपको एल्गोरिदम के गतिशील प्रोग्रामिंग संस्करण के लिए लागू करने की आवश्यकता होती है। अपने तारों की लंबाई के आधार पर, यह पूरी तरह से संभव है कि गतिशील प्रोग्रामिंग तेज़ी से हो जाएगी।

गुड लक :)

Answer 2

ये यह तेजी से चलाने कर देगा, हालांकि यह अभी भी O(nm) हो जाएगा।

एक अनुकूलन अंतरिक्ष में है (यदि आप एक छोटे से आवंटन समय बचाने के लिए हो सकता है) देख रहा है कि LCSuff केवल पिछली पंक्ति पर निर्भर करता है - इसलिए यदि आप केवल लंबाई के बारे में परवाह है, तो आप O(min(n,m)) करने के लिए नीचे O(nm) अंतरिक्ष का अनुकूलन कर सकते हैं। वर्तमान पंक्ति है कि आप कार्रवाई कर रहे हैं, और पिछली पंक्ति है कि आप बस संसाधित, और बाकी फेंक -

विचार केवल दो पंक्तियों रखने के लिए है।

Answer 3

Myer's bit vector algorithm आप कर सकते हैं। यह बिट मैनिप्ल्यूशन का उपयोग करके काम करता है और यह एक बहुत तेज दृष्टिकोण है।

Answer 4

यहाँ एक सरल एल्गोरिथ्म है जो कर सकते हैं हे में खत्म ((m + n) * लॉग (m + n)), और बहुत आसान प्रत्यय पेड़ एल्गोरिथ्म की तुलना में लागू करने के लिए जो ओ (m + n) क्रम है।

इसे न्यूनतम सामान्य लंबाई (minL) = 0, और अधिकतम सामान्य लंबाई (maxL) = min (m + n) +1 से शुरू करने दें।

1. if (minL == maxL - 1), the algorithm finished with common len = minL. 

2. let L = (minL + maxL)/2 

3. hash every substring of length L in S, with key = hash, val = startIndex. 

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1. 

शेष समस्या यह है कि समय ओ (एन) में लंबाई एल के साथ सभी सबस्ट्रिंग हैश को कैसे है। आप इस प्रकार एक बहुपद सूत्र का उपयोग कर सकते हैं:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p. 

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];