Bạn đọc bản dịch này bằng các ngôn ngữ khác: English
Bài toán dãy con chung dài nhất (LCS) là bài toán tìm dãy con dài nhất chung cho tất cả các dãy trong một tập hợp các dãy (thường chỉ là hai dãy). Nó khác với bài toán dãy con chung dài nhất: so với các dãy con, các dãy con không yêu cầu chiếm vị trí liên tiếp trong các dãy gốc.
Bài toán dãy con chung dài nhất là một bài toán kinh điển trong khoa học máy tính, là cơ sở của các chương trình so sánh dữ liệu như tiện ích diff, và có ứng dụng trong sinh học tin học. Nó cũng được sử dụng rộng rãi bởi các hệ thống kiểm soát phiên bản như Git để điều hòa nhiều thay đổi được thực hiện đối với một bộ sưu tập các tập tin được kiểm soát bản.
- LCS cho các dãy đầu vào
ABCDGHvàAEDFHRlàADHcó độ dài là 3. - LCS cho các dãy đầu vào
AGGTABvàGXTXAYBlàGTABcó độ dài là 4.