Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में दो से अधिक स्ट्रिंग्स से सबसे लंबी सामान्य सबस्ट्रिंग कैसे खोजें

लॉन्गेस्ट कॉमन सबस्ट्रिंग एल्गोरिदम के सामान्य डायनामिक प्रोग्रामिंग कार्यान्वयन O(nm) समय में चलते हैं। लॉन्गेस्ट कॉमन सबस्ट्रिंग एल्गोरिदम का निम्नलिखित कार्यान्वयन है:

उदाहरण

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in range(1, 1 + len(s1)):
        for y in range(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

print(longest_common_substring('wellbeing', 'welcome'))

आउटपुट

wel

यह ऐसे काम करता है:

  • प्रारंभ में, हमने काउंटर सरणी (m) को सभी 0 से इनिशियलाइज़ किया।

  • पहली पंक्ति से शुरू करके, हम स्ट्रिंग s1 के पहले वर्ण की तुलना स्ट्रिंग s2 के सभी वर्णों से करेंगे।

  • जब हम s2 में वर्णों को पार करते हैं, यदि यह s1 में वर्ण से मेल खाता है, तो हम काउंटर बढ़ाते हैं। इसे विकर्ण रूप से एक निचली स्थिति m[i][j] पर सहेजा जाएगा।

अंत में हम लूप में गणना किए गए इंडेक्स का उपयोग करके सबसे लंबी सब-स्ट्रिंग वापस करते हैं।

  1. Python में स्रोत से k लंबाई से अधिक पथ है या नहीं ढूंढना Python में स्रोत से k लंबाई से अधिक पथ है या नहीं ढूंढना

    मान लीजिए हमारे पास एक ग्राफ है, हमारे पास एक स्रोत शीर्ष और एक संख्या k भी है। k स्रोत से गंतव्य तक ग्राफ का पथ लंबाई है, हमें जांचना है कि क्या हम स्रोत से शुरू होने वाला और किसी अन्य शीर्ष (गंतव्य के रूप में) पर समाप्त होने वाला एक सरल पथ (बिना चक्र के) ढूंढ सकते हैं। ग्राफ निम्नलिखित में दिखाया

  1. पायथन प्रोग्राम: दो स्ट्रिंग्स से असामान्य शब्द खोजें पायथन प्रोग्राम: दो स्ट्रिंग्स से असामान्य शब्द खोजें

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें दो स्ट्रिंग्स दी गई हैं, हमें दी गई स्ट्रिंग्स से असामान्य शब्द प्राप्त करने हैं। उदाहरण # असामान्य शब्द def find(A, B): # काउंट count = {} # A में डालें for word in A.split(): count[word] = count.get(w

  1. पायथन प्रोग्राम: दो क्रमबद्ध सरणियों से निकटतम जोड़ी खोजें पायथन प्रोग्राम: दो क्रमबद्ध सरणियों से निकटतम जोड़ी खोजें

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें दो सरणियाँ दी गई हैं, हमें दो क्रमबद्ध सरणियों से निकटतम जोड़ी खोजने की आवश्यकता है। उदाहरण # sys मॉड्यूल import sys # जोड़ी def print_(ar1, ar2, m, n, x): # अंतर diff = sys.maxsize # इंडेक्स l = 0 r = n-1