Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mẫu với Thuật toán tìm kiếm Knuth Morris Pratt Thuật toán tìm kiếm Knuth Morris Pratt (KMP) Đặc điểm: – Thực hiện phép so sánh từ trái sang phải – Pha tiền xử lí có độ phức tạp về không gian và thời gian là Read more about Thuật toán tìm kiếm Knuth Morris Pratt[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mẫu với Thuật toán tìm kiếm Morris Pratt, cài đặt bằng Java Thuật toán tìm kiếm Morris Pratt Đặc điểm: – Thực hiện phép so sánh từ trái sang phải – Pha tiền xử lí có độ phức tạp về không gian và thời gian Read more about Thuật toán tìm kiếm Morris Pratt[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau; tìm kiếm mẫu với thuật toán tìm kiếm Tuned Boyer Moore Thuật toán tìm kiếm Tuned Boyer Moore Đặc điểm: +Chỉ sử dụng the bad-character shift +Dễ cài đặt +Độ phức tạp thuật toán là O(m.n) Input: Xâu mẫu x=(x0,x1,…,xm-1) độ dài m Xâu văn Read more about Thuật toán tìm kiếm Tuned Boyer Moore[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mấu bằng thuật toán tìm kiếm Smith, cài đặt Smith bằng Java Thuật toán tìm kiếm Smith Kết hợp 2 thuật toán QuickSearch và Horspool, tại mỗi bước nhảy sẽ kiểm tra xem nhảy theo QuickSearch hay Horspool xa hơn thì chọn. Đặc điểm: Read more about Thuật toán tìm kiếm Smith[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mẫu với thuật toán tìm kiếm Quick Search Thuật toán tìm kiếm Quick Search Đặc điểm: +Chỉ sử dụng the bad-character shift +Dễ cài đặt +Độ phức tạp thuật toán là O(m.n) Input: Xâu mẫu x=(x0,x1,…,xm-1) độ dài m Xâu văn bản: y= Read more about Thuật toán tìm kiếm QuickSearch[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau Lấy l=0 nếu x là một tập của cùng một ký tự và l được tính bằng vị trí của ký tự đầu tiên khác x[0] trong các trường hợp khác. Trong suốt thuật toán xét 3 trường hợp: -Vị trí xét nằm trong khoảng y[j..j+m-1] Read more about Thuật toán tìm kiếm Apostolico-Crochemore[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mẫu với thuật toán tìm kiếm Raita, cài đặt Raita bằng Java. Thuật toán tìm kiếm Raita Cải thiện từ thuật toán Horspool, trước khi so sánh 2 mảng với nhau thì ta so sánh 2 kí tự đầu nếu giống nhau thì so Read more about Thuật toán tìm kiếm Raita[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mẫu với thuật toán tìm kiếm Horspool Thuật toán sẽ quét các ký tự của mẫu (pattern) từ phải sang trái bắt đầu ở phần tử cuối cùng. Đối với mẫu x[0..m-1] ta dùng 1 biến chỉ số i chạy từ cuối về đầu, Read more about Thuật toán tìm kiếm Horspool[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mẫu với thuật toán tìm kiếm Not So Naive. Thuật toán tìm kiếm Not So Naive Cải tiến từ Brute Force, khi x so khớp với y nằm trong khoảng [j..j+m-1]. Nếu x[0]=x[1] và x[1]<>y[j+1] hoặc x[0]<>x[1] và x[1]=y[j+1] thì dịch chuyển sang phải Read more about Thuật toán tìm kiếm Not So Naive[…]
Giới thiệu về bài toán tìm kiếm mẫu, string: https://stackjava.com/mot-so-thuat-toan-tim-kiem-mau, tìm kiếm mẫu với thuật toán tìm kiếm Brute Force, Brute Force trong Java Lần lượt xét từng vị trí i trong xâu ký tự gốc từ 0 đến n-m, so sánh y[i…(i+m-1)] với x[0…m-1] bằng cách xét từng cặp ký tự một và đưa ra kết Read more about Thuật toán tìm kiếm Brute Force[…]
