tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm chuỗi - Nguyễn Tri Tuấn

Bài giảng "Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm chuỗi" cung cấp cho người học các kiến thức mở đầu về string searching, các bước xử lý, các cách tiếp cận, Brute-Force, Knuth-Morris-Pratt. . | Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm chuỗi - Nguyễn Tri Tuấn Data Structures & Algorithms Các thuật toán tìm kiếm chuỗi (String Searching Algorithms) Nguyễn Tri Tuấn Khoa CNTT – Email: nttuan@ String Searching Giới thiệu Các bước xử lý Các cách tiếp cận Brute-Force Knuth-Morris-Pratt Autumn 2008 Data Structures & Algorithms - String Searching - Nguyen Tri Tuan, 2 Brute-Force Ý tưởng: Đối với vị trí thứ i của văn bản T (i=0 n-m), ta so sánh các ký tự của P tương ứng từ trái sang phải: P[0] với T[i], P[1] với T[i+1], , P[m-1] với T[i+m-1] P[j] với T[i+j] (j = 0m-1) Ví dụ: T = “TWO RED ROADS CROSSING” n = length(T) = 22 P = “ROADS” m = length(P) = 5 Autumn 2008 Data Structures & Algorithms - String Searching - Nguyen Tri Tuan, 3 Brute-Force (tt) Ví dụ: Bước 1: TWO RED ROADS CROSSING ROADS Bước 2: TWO RED ROADS CROSSING ROADS Bước 5: TWO RED ROADS CROSSING ROADS Bước 9: TWO RED ROADS CROSSING ROADS Autumn 2008 Data Structures & Algorithms - String Searching - Nguyen Tri Tuan, 4 Brute-Force (tt) Cài đặt bằng C: int stringSearchBF (char *P, char *T); Kết quả: -1 : nếu P không nằm trong T, hoặc >=0: vị trí của P trong T Autumn 2008 Data Structures & Algorithms - String Searching - Nguyen Tri Tuan, 5 Brute-Force (tt) int stringSearchBF(char *P, char *T) { for (int i=0; i Brute-Force (tt) Đánh giá: Trường hợp xấu nhất O(m*n) – tự chứng minh Autumn 2008 Data Structures & Algorithms - String Searching - Nguyen Tri Tuan, .