Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 ĐH.KHTN.Tp.HCM Email nttuan@fit.hcmus.edu.vn CuuDuongThanCong.com https fb.com 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 DH.KHTN Tp.HCM 2 CuuDuongThanCong.com https fb.com 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 0.m-1 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 DH.KHTN Tp.HCM 3 CuuDuongThanCong.com https fb.com 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 DH.KHTN Tp.HCM 4 CuuDuongThanCong.com https fb.com 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 DH.KHTN Tp.HCM 5 CuuDuongThanCong.com https fb.com 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 DH.KHTN Tp.HCM 7 CuuDuongThanCong.com https fb.com 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 DH.KHTN Tp.HCM 8 CuuDuongThanCong.com https fb.com tailieudientucntt String Searching Giới .
