longest-common-subsequence

Bài toán chuỗi con chung dài nhất

Vấn đề chuỗi con chung dài nhất (LCS) là vấn đề trong việc tìm kiếm một chuỗi con chung dài nhất cho tất cả các chuỗi trong một bộ chuỗi (thường chỉ hai chuỗi). Nó khác với vấn đề về xâu con chung dài nhất ở chỗ: không giống như các xâu con, các chuỗi con không bắt buộc phải chiếm các vị trí liên tiếp trong các chuỗi ban đầu.

Ứng dụng

Bài toán chuỗi con chung dài nhất là một trong những bài toán khoa học máy tính cổ điển, là cơ sở của các chương trình so sánh dữ liệu như diff, và có các ứng dụng trong ngôn ngữ học tính toán và tin sinh học.

Nó cũng được sử dụng rộng rãi bởi các hệ thống quản lý phiên bản như Git để điều chỉnh nhiều thay đổi được thực hiện cho một bộ sưu tập tệp được kiểm soát sửa đổi.

Ví dụ

• LCS của chuỗi đầu vào ABCDGH và AEDFHR là ADH có độ dài là 3.
• LCS của chuỗi đầu vào AGGTAB và GXTXAYB là GTAB có độ dài là 4.

Liên kết

• Wikipedia
• YouTube