एन स्ट्रिंग्स

Question

में सामान्य सबस्ट्रिंग खोजने के लिए एल्गोरिदम मैं 2 तारों के लिए एलसीएस एल्गोरिदम से परिचित हूं। 2. स्ट्रिंग्स में सामान्य सबस्ट्रिंग खोजने के लिए सुझाव ढूंढ रहे हैं। प्रत्येक जोड़ी में कई सामान्य सबस्ट्रिंग हो सकते हैं। तारों के सबसेट में अलग-अलग सामान्य सबस्ट्रिंग हो सकते हैं।

तार: (ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)

आम तार:

1/2 (DEF) 
1/3 (ABCDEF) 
1/4 (IJKL) 
1/5 (FGH) 
2/3 (DEF) 

सबसे लंबे समय तक आम तार:

1/3 (ABCDEF) 

सबसे आम तार:

1/2/3 (DEF) 

Answer 1

इस सोर डीएनए अनुक्रम विश्लेषण में हर समय चीज की जाती है। आप इसके लिए विभिन्न एल्गोरिदम पा सकते हैं। एक उचित संग्रह here सूचीबद्ध है। प्रत्येक में एक एन-ary पेड़ फार्म (N = 26 अक्षर के लिए, ASCII के लिए 256):

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

Answer 2

सफ़िक्स पेड़ उत्तर हैं जब तक कि आपके पास वास्तव में बड़े स्ट्रिंग नहीं होते हैं जहां स्मृति एक समस्या बन जाती है। एक अच्छा कार्यान्वयन के लिए स्ट्रिंग में प्रति चरित्र स्मृति उपयोग के 10 ~ 30 बाइट की अपेक्षा करें। कुछ खुले स्रोत कार्यान्वयन भी हैं, जो आपके काम को आसान बनाते हैं।

अन्य, अधिक succint एल्गोरिदम भी हैं, लेकिन वे लागू करने के लिए कठिन हैं ("संपीड़ित प्रत्यय पेड़" के लिए देखो)।