Khi cần tìm chuỗi con chung dài nhất bằng cách sử dụng lập trình động với cách tiếp cận từ dưới lên, một phương pháp có thể được xác định, tính toán giải pháp cho các vấn đề nhỏ hơn. Các kết quả vấn đề nhỏ hơn này không cần phải tính toán lại nhiều lần. Thay vào đó, chúng chỉ có thể được truy cập khi được yêu cầu. Điều này sẽ dẫn đến việc phát triển một giải pháp cho vấn đề lớn hơn.
Dưới đây là một minh chứng cho điều tương tự -
Ví dụ
def compute_lcw(string_1, string_2):
val = [[-1]*(len(string_2) + 1) for _ in range(len(string_1) + 1)]
for i in range(len(string_1) + 1):
val[i][len(string_2)] = 0
for j in range(len(string_2)):
val[len(string_1)][j] = 0
lcw_i = lcw_j = -1
lcw_len = 0
for i in range(len(string_1) - 1, -1, -1):
for j in range(len(string_2)):
if string_1[i] != string_2[j]:
val[i][j] = 0
else:
val[i][j] = 1 + val[i + 1][j + 1]
if lcw_len < val[i][j]:
lcw_len = val[i][j]
lcw_i = i
lcw_j = j
return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("The longest common substring is : ")
if lcw_len > 0:
print(string_1[lcw_i:lcw_i + lcw_len]) Đầu ra
The longest common substring is : bull
Giải thích
- Một phương thức có tên 'compute_lcw' được xác định, có hai chuỗi làm tham số.
- Hai chuỗi được lặp lại và kiểm tra xem có tìm thấy bất kỳ chuỗi phù hợp nào trong cả hai chuỗi hay không.
- Ngay cả khi một ký tự được tìm thấy, nó sẽ được lưu trữ trong một biến khác.
- Khi điều này tiếp diễn cho đến cuối chuỗi, một chuỗi khác sẽ là chung cho cả hai chuỗi này.
- Hai chuỗi được xác định và phương thức được gọi bằng cách chuyển hai chuỗi này.
- Dữ liệu của thao tác này được gán cho một biến.
- Sau đó, nó được hiển thị dưới dạng đầu ra trên bảng điều khiển.