Bài giảng "Cấu trúc dữ liệu và giải thuật: Đối sách chuỗi" đã giới thiệu những kiến thức cơ bản về đối sách chuỗi, thuật toán Brute-Force, thuật toán Morris-Pratt, cải tiến với Knuth-Morris-Pratt, . Mời các bạn cùng tham khảo. | Giảng viên Văn Chí Nam Nguyễn Thị Hồng Nhung Đặng Nguyễn Đức Tiến Giới thiệu Thuật toán Brute-Force Thuật toán Morris-Pratt Cải tiến với Knuth-Morris-Pratt Thuật toán Rabin-Karp Cấu trúc dữ liệu và giải thuật - HCMUS 2015 https tailieudientucntt FIT-HCMUS 1 Đối sánh chuỗi Từkhóa String matching String searching Pattern searching Text Searching Mộttrong những thuật toán quan trọng và có ứng dụng rộng rãi. Cấu trúc dữ liệu và giải thuật - HCMUS 2015 Ứng dụng của đối sánh chuỗi Máy tìm kiếm Trình soạn thảo văn bản Trình duyệt web Sinh học phân tử Tìm mẫu trong dãy DNA . . Cấu trúc dữ liệu và giải thuật - HCMUS 2015 https tailieudientucntt FIT-HCMUS 2 Mục tiêu Kiểm tra sự tồn tại của một chuỗi ký tự mẫu pattern trong một chuỗi ký tự có kích thước lớn hơn nhiều văn bản text . Nếu tồn tại trả về một hoặc nhiều vị trí xuất hiện. Quy ước Mẫu cần tìm P chiều dài m . Văn bản T chiều dài n . P và T có cùng tập hữu hạn ký tự . 0 1 A . Z m n Cấu trúc dữ liệu và giải thuật - HCMUS 2015 Đối sánh chuỗi Bằng cách lần lượt dịch chuyển cửa sổ P trên T. P tồn tại trên T tại vị trí bắt đầu là i 0 i n m nếu T i j P j với mọi 0 j m - 1. Ví dụ P abbaba T ababaabbabaa gt i 5 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 https tailieudientucntt FIT-HCMUS 3 Các thuật toán tiêu biểu BruteForce Morris-Pratt Knuth-Morris-Pratt Rabin-Karp Boyer-Moore Cấu trúc dữ liệu và giải thuật - HCMUS 2015 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 https tailieudientucntt FIT-HCMUS 4 Lần lượt kiểm tra điều kiện P 0 m-1 T i i m-1 tại mọi vị trí có thể của i. Ví dụ Tìm kiếm P aab trong T acaabc Cấu trúc dữ liệu và giải thuật - HCMUS 2015 bruteForceMatcher T P n length T m length P for i 0 to n - m if P T i i m-1 return i Cấu trúc dữ liệu và giải thuật - HCMUS 2015 https tailieudientucntt FIT-HCMUS 5 Trường hợp tốt nhất không tìm thấy O n . Trường hợp xấu nhất không .
