TAILIEUCHUNG - 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, .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Data structures
• Các thuật toán tìm kiếm chuỗi
• String searching algorithms
• String searching
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp