Triển khai lập trình động phổ biến cho thuật toán Chuỗi con chung dài nhất chạy trong thời gian O (nm). Sau đây là cách triển khai thuật toán chuỗi con chung dài nhất:
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')) Đầu ra
wel
Đây là cách nó hoạt động
-
Ban đầu, chúng tôi khởi tạo mảng bộ đếm (m) tất cả là 0.
-
Bắt đầu từ hàng đầu tiên, chúng tôi sẽ so sánh ký tự đầu tiên của chuỗi s1 với tất cả các ký tự trong chuỗi s2.
-
Trong khi chúng tôi duyệt các ký tự trong s2, nếu nó khớp với ký tự trong s1, chúng tôi tăng bộ đếm. Nó sẽ được lưu m [i] [j] ở vị trí chéo một phía dưới.
Cuối cùng, chúng tôi trả về chuỗi con dài nhất bằng cách sử dụng các chỉ số mà chúng tôi đã tính toán trong các vòng lặp.