Chuỗi con chung dài nhất (LCS): Git biết bạn sửa dòng nào

``` Em thêm một dòng chú thích, sửa một dòng cộng dồn — git diff chỉ ra đúng ba dòng đổi. Nó làm thế nào? Video đi từ hai chuỗi tí hon ABC và BDC tới ví dụ trên lớp ABCBDAB và BDCAB: vì sao so từng dòng cùng số thứ tự là hỏng, chuỗi con khác chuỗi con liền ở đâu, vì sao thử hết mọi chuỗi con gấp đôi theo mỗi chữ, nhìn chữ cuối để chia bài toán, vì sao gọi đệ quy thẳng giải một bài con nhiều lần, và cách ghi bài con vào bảng để mỗi ô chỉ tốn một lần so. Có một chỗ dừng lại để em tự điền một ô, và một lần truy vết ra hai đáp án đều đúng. Hai tệp bốn mươi dòng: 1 600 lần so thay vì hơn một nghìn tỉ chuỗi con. Video bổ trợ Buổi 6 học phần Phân tích & Thiết kế Giải thuật (COS157), Khoa Công nghệ Thông tin, HUTECH. Mục lục 0:00 Mở đầu 0:27 So từng dòng 1:03 Chuỗi con 1:43 Thử hết 2:16 Chữ cuối 3:00 Ghi vào bảng 3:50 Dừng lại thử 4:13 Bảng tí hon 4:59 Bảng đầy đủ 5:47 Truy vết 6:24 Quay về Git 6:54 Đếm ô 7:28 Ngoài đời thực 7:53 Ba điều mang về Mô phỏng lấp bảng từng ô: Bu6_lcs_matrix.html — Tab 1, X = ABCBDAB, Y = BDCAB, rồi bấm "Truy vết nghiệm" (LMS Buổi 6) Video trước: V06 Quy hoạch động: Fibonacci & ghi nhớ · Video tiếp: V07 Cái túi 0/1 Tài liệu · T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., §15.4 Longest common subsequence · A. Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed., Ch. 8 Dynamic Programming · J. W. Hunt, M. D. McIlroy, An Algorithm for Differential File Comparison, Computing Science Technical Report No. 41, Bell Laboratories, 1976 · E. W. Myers, An O(ND) Difference Algorithm and Its Variations, Algorithmica 1, 1986, 251–266 · git-diff(1), tuỳ chọn --diff-algorithm và --minimal #LCS #ChuoiConChungDaiNhat #QuyHoachDong #GitDiff #ThuatToan #COS157 #HUTECH ```