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. Mời các bạn cùng tham khảo. | Data Structures amp 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@ https tailieudientucntt 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 amp Algorithms - String Searching - Nguyen Tri Tuan 2 https tailieudientucntt 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 Ví dụ T TWO RED ROADS CROSSING n length T 22 P ROADS m length P 5 Autumn 2008 Data Structures amp Algorithms - String Searching - Nguyen Tri Tuan 3 https tailieudientucntt 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 amp Algorithms - String Searching - Nguyen Tri Tuan 4 https tailieudientucntt 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 gt 0 vị trí của P trong T Autumn 2008 Data Structures amp Algorithms - String Searching - Nguyen Tri Tuan 5 https tailieudientucntt 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 amp Algorithms - String Searching - Nguyen Tri Tuan 7 https tailieudientucntt Brute-Force tt Đánh giá Trường hợp tốt nhất O n tự chứng minh Trường hợp trung bình O n m tự chứng minh Autumn 2008 Data Structures amp Algorithms - String Searching - Nguyen Tri Tuan 8 https tailieudientucntt String Searching Giới .