लॉन्गेस्ट कॉमन सबस्ट्रिंग एल्गोरिदम के सामान्य डायनामिक प्रोग्रामिंग कार्यान्वयन 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] पर सहेजा जाएगा।
अंत में हम लूप में गणना किए गए इंडेक्स का उपयोग करके सबसे लंबी सब-स्ट्रिंग वापस करते हैं।