Bài toán tìm xâu con chung dài nhất

Trong xử lý văn bản nói chung và mã nguồn chương trình nói riêng, việc tìm ra những phần giống nhau trong các văn bản hay mã nguồn chương trình có vai trò khá quan trọng, nhất là khi cần phát hiện sự sao chép code. Trong bài viết này, chúng tôi muốn giới thiệu thuật toán và các phương pháp xử lí liên quan nhằm tìm ra những phần giống nhau trong các code với độ phức tạp về mặt thời gian và chi phí bộ nhớ là tuyến tính, độ chính xác cao kể cả trong một số trường hợp đặc biệt.

5p cumeo2004 02-07-2018 59 3   Download

Bài giảng gồm các bài tập minh họa cho phương pháp Qui hoạch động: bài toán tìm xâu con chung dài nhất, đường đi ngắn nhất - Thuật toán Floyd và bài toán cây nhị phân tìm kiếm tối ưu. Tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin. Mời các bạn cùng tham khảo.

18p hetiheti 04-03-2017 82 4   Download

Cho hai xâu X =x1x2…xm và Y=y1y2…yn. Tìm xâu Z = z1z2…zk là xâu con chung dài nhất của X và Y. Một xâu con của xâu A là một cách chọn trong A một số phần tử giữ nguyên thứ tự. Bảng phương án Ta sẽ dùng mảng hai chiều B[0..m, 0..n] làm bảng phương án, trong đó B[i,j] là độ dài xâu chung dài nhất của các xâu con Xi (phần đầu của X) và Yj (phần đầu của Y). Cơ sở Rõ ràng nếu ít nhất một trong hai xâu X hoặc Y là xâu rỗng...

5p abcdef_45 29-10-2011 1271 83   Download