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,. . | Bài giảng Cấu trúc dữ liệu và giải thuật: Đối sách chuỗi - Văn Chí Nam, Nguyễn Thị Hồng Nhung, Đặng Nguyễn Đức Tiến 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 © 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 © 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 => i = 5 Cấu trúc dữ liệu và giải thuật - HCMUS 2015 © 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 © .
