Ô đã điền
Cặp khớp
Dài nhất hiện tại

  • Đang điền
  • Được đọc
  • Đáp án

Thêm về dãy con chung dài nhất

Dãy con chung dài nhất (LCS)

Hai từ có những chữ cái nào chung, theo cùng thứ tự? Dãy con chung dài nhất trả lời câu hỏi đó, và các công cụ diff, trình kiểm tra chính tả hay việc so sánh DNA đều dựa trên nó. Nhập hai từ, xem bảng các chữ cái của chúng được điền dần, rồi lần ngược đáp án từ góc bảng. Nhấn Phát để xem bảng được điền dần, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Nhập hai từ: từ thứ nhất xếp dọc xuống ở bên cạnh bảng, từ thứ hai xếp ngang dọc theo phía trên. Mỗi ô chứa độ dài dãy con chung dài nhất của các chữ cái tính đến hàng và cột của ô đó. Cuối cùng, các chữ cái được đọc ngược từ ô dưới cùng bên phải. Ví dụ mới chọn một cặp từ khác. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.

Cách nó hoạt động

  1. Nhập hai từ: từ thứ nhất xếp dọc xuống ở bên cạnh bảng, từ thứ hai xếp ngang dọc theo phía trên.
  2. Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu.
  3. Xem mỗi ô so sánh hai chữ cái của nó, rồi đi theo đường màu cam ngược từ góc bảng để đọc đáp án.

Cách bảng hoạt động

Một ô chứa độ dài dãy con chung dài nhất giữa các chữ cái của từ thứ nhất tính đến hàng của ô và các chữ cái của từ thứ hai tính đến cột của ô. Hàng và cột được đánh dấu – đại diện cho một từ rỗng, nên chúng bằng 0. Nếu hai chữ cái của một ô bằng nhau, ô đó lớn hơn ô phía trên bên trái một đơn vị. Nếu chúng khác nhau, một trong hai chữ không thuộc đáp án, nên ô lấy giá trị lớn hơn giữa ô phía trên và ô bên trái.

Đọc ngược các chữ cái

Ô dưới cùng bên phải là độ dài của đáp án. Để tìm các chữ cái, hãy bắt đầu từ đó: ở chỗ hai chữ cái khớp nhau, chữ đó thuộc dãy con và ta đi lên phía trên bên trái; nếu không, ta đi sang ô lớn hơn giữa ô phía trên và ô bên trái. Các chữ cái thu được trên đường đi, đọc theo thứ tự ngược lại, tạo thành một dãy con chung dài nhất. Có thể còn những dãy khác cùng độ dài; cách đọc ngược tìm ra một trong số đó.

Câu hỏi thường gặp

Dãy con khác xâu con như thế nào?

Xâu con là một đoạn chữ cái đứng liền nhau, như ACE trong RACER. Dãy con giữ thứ tự nhưng có thể bỏ qua chữ cái, nên ACE cũng là dãy con của ABCDE. Xâu con chung dài nhất là một bài toán khác, dùng một bảng tương tự.

Thuật toán LCS nhanh đến mức nào?

Với hai từ có độ dài m và n, bảng có m·n ô, mỗi ô được điền trong một bước, nên khối lượng công việc là O(m·n). Với hai văn bản 10.000 dòng, con số đó là 100 triệu ô, vì vậy các công cụ diff dùng những phương pháp khéo léo hơn dựa trên cùng ý tưởng.

Dãy con chung dài nhất có duy nhất không?

Không. ABCBDAB và BDCABA có ba dãy con chung khác nhau độ dài 4: BCBA, BCAB và BDAB. Bảng cho biết độ dài; cách đọc ngược chọn ra một trong số đó.

LCS có cho biết hai từ giống nhau đến mức nào không?

Một phần. Hai từ có độ dài m và n với dãy con chung dài nhất độ dài k có thể biến thành nhau bằng cách xóa m − k chữ cái và chèn n − k chữ cái. Khoảng cách chỉnh sửa, vốn cho phép cả thay thế một chữ cái, thường là thước đo tốt hơn.

Có dữ liệu nào được gửi đi đâu không?

Không. Mọi thứ được tính toán ngay trong trình duyệt của bạn, và các cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa