Nội dung nghiên cứu đề tài trình bày về tìm kiếm mẫu từ trái qua phải; tìm kiếm mẫu từ phải qua trái; tìm kiếm mẫu từ vị trí cụ thể; tìm kiếm mẫu từ vị trí bất kì. Mời các bạn cùng tham khảo! | PoppinKhiem HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG KHOA CÔNG NGHỆ THÔNG TIN 1 BÁO CÁO MÔN CHUYÊN ĐỀ CÔNG NGHỆ PHẦN MỀM CHỦ ĐỀ PATTERN SEARCHING Giảng viên Nguyễn Duy Phương Sinh viên Mã SV B52 Nhóm MH 1 PoppinKhiem Hà Nội 3 7 2021 2 PoppinKhiem Muc luc ̣ ̣ I. Tim kiêm mâu t ̀ ́ ̃ ừ trai qua phai ́ ̉ 1. Thuật toán Brute Force. 2. Thuật toán Knuth Morris Pratt. 3. Thuật toán Karp Rabin. 4. Thuật toán Morris Pratt. 5. Thuật toán Search with an automaton. II. Tìm kiêm mâu t ́ ̃ ừ phai qua trai ̉ ́ 1. Thuật toán Boyer Moore. 2. Thuật toán Turbo Boyer Moore. 3. Zhu Takaota. 4. Thuật toán Berry Ravindran . 5. Thuật toán Apostollico giancarlo. 6. Thuật toán Colussi. III. Tim kiêm mâu t ̀ ́ ̃ ừ vi tri cu thê ̣ ́ ̣ ̉ 1. Thuật toán Skip Search. 2. Thuật toán Galil Giancarlo. IV. Tim kiê ̀ ́m mâu t ̃ ư vi tri bât ki ̀ ̣ ́ ́ ̀ 1. Thuật toán Quick Search. 2. Thuật toán Smith. 3. Thuật toán Raita. 4. Thuật toán HorsePool. 3 PoppinKhiem I. Tìm kiếm mẫu từ trái qua phải 1. Thuật toán Brute Force Đặc điểm Không có giai đoạn tiền xử lý Bộ nhớ cần dùng cố định Luôn luôn dịch 1 bước sang phải Việc so sánh có thể phải dùng trong các trường hợp Độ phức tạp pha thực thi là O m x n So sánh khoảng 2n ký tự Trình bày thuật toán Thuật toán Brute Force kiểm tra ở tất cả các vị trí trong đoạn văn bản giữa 0 và n m không cần quan tâm liệu mẫu này có tồn tại ở vị trí đó hay không. Sau đó sau mỗi lần kiểm tra mẫu sẽ dịch sang phải một vị trí. Thuật toán Brute Force không cần giai đoạn tiền xử lý cũng như các mảng phụ cho quá trình tìm kiếm. Độ phức tạp tính toán của thuật toán này là O . Code void BruteForce char x int m char y int n for int i 0 PoppinKhiem Kiểm nghiệm thuật toán Xâu X AB Xâu Y ABDAAB 1 Y A B D A A B X A 1 B 2 2 Y A B D A A B X A B 3 Y A B D A A B X A 4 Y A B D A A B X A 1 B 5 Y A B D A A B X A 1 B 2 2. Thuật toán Knuth Morris Pratt Đặc điểm Thực hiện từ trái qua phải Pha tiền xử lý PreKMP có độ phức tạp không .
