Đề tài Pattern searching

  • Người chia sẻ : vtlong
  • Số trang : 57 trang
  • Lượt xem : 20
  • Lượt tải : 500
  • Tất cả luận văn được sưu tầm từ nhiều nguồn, chúng tôi không chịu trách nhiệm bản quyền nếu bạn sử dụng vào mục đích thương mại

NHẬP MÃ XÁC NHẬN ĐỂ TẢI LUẬN VĂN NÀY

Nếu bạn thấy thông báo hết nhiệm vụ vui lòng tải lại trang

Bạn đang xem trước 20 trang tài liệu Đề tài Pattern searching, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD LUẬN VĂN ở trên

 Đặ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(m.n).