Tìm longest common substring từ nhiều string Python

Common dynamic programming implementation cho thuật toán Longest Common Substring chạy trong O(nm) time. Implementation sau:

Ví dụ

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in xrange(1, 1 + len(s1)):
        for y in xrange(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'))

Output

wel

Cách hoạt động:

• Khởi tạo counter array m toàn 0.
• Từ row 1, so sánh ký tự đầu của s1 với tất cả ký tự trong s2.
• Khi traverse ký tự trong s2, nếu match ký tự trong s1, increment counter. Lưu ở m[i][j] vị trí chéo dưới.

Cuối cùng trả về longest sub-string dùng index tính trong loops.