Lập trình Java

Thuật toán Boyer-Moore trong Java

Posted on by Đỗ Thành
Lập trình Java
07
Th5
View: 71

Thuật toán Boyer-Moore là một thuật toán tìm kiếm chuỗi trong chuỗi, được phát triển bởi Robert S. Boyer và J Strother Moore vào năm 1977. Thuật toán này cho phép tìm kiếm với độ phức tạp thấp hơn so với các thuật toán khác như Brute Force hay KMP.

Thuật toán Boyer-Moore dựa trên việc so sánh các ký tự trong chuỗi mẫu với các ký tự trong chuỗi cần tìm kiếm từ phải sang trái. Nếu có sự khác biệt giữa hai ký tự, thuật toán sẽ sử dụng hai bảng phụ để xác định khoảng cách cần phải di chuyển.

Bảng đầu tiên được gọi là bảng chữ cái và lưu trữ khoảng cách từ ký tự được so sánh đến ký tự cuối cùng của chuỗi mẫu. Bảng thứ hai được gọi là bảng hậu tố và lưu trữ khoảng cách từ ký tự bị sai khác cuối cùng trong chuỗi mẫu đến ký tự cuối cùng của chuỗi mẫu.

Sau khi xác định khoảng cách cần phải di chuyển, thuật toán sẽ thực hiện việc di chuyển con trỏ của chuỗi cần tìm kiếm tương ứng. Nếu không có ký tự khác biệt nào, thuật toán sẽ tiến hành tìm kiếm tiếp theo.

Dưới đây là một ví dụ về cách triển khai thuật toán Boyer-Moore trong Java:

public class BoyerMoore {
    private int[] right;
    private String pat;

    public BoyerMoore(String pat) {
        this.pat = pat;
        int m = pat.length();
        int R = 256;
        right = new int[R];
        for (int i = 0; i < R; i++) {
            right[i] = -1;
        }
        for (int i = 0; i < m; i++) {
            right[pat.charAt(i)] = i;
        }
    }

    public int search(String txt) {
        int n = txt.length();
        int m = pat.length();
        int skip;
        for (int i = 0; i <= n - m; i += skip) {
            skip = 0;
            for (int j = m - 1; j >= 0; j--) {
                if (pat.charAt(j) != txt.charAt(i + j)) {
                    skip = Math.max(1, j - right[txt.charAt(i + j)]);
                    break;
                }
            }
            if (skip == 0) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String txt = "ABAAABCD";
        String pat = "ABC";
        BoyerMoore bm = new BoyerMoore(pat);
        int offset = bm.search(txt);
        if (offset == -1) {
            System.out.println("Pattern not found");
        } else {
            System.out.println("Pattern found at index " + offset);
        }
    }
}

Trong đó, phương thức khởi tạo BoyerMoore dùng để tạo ra bảng phân tích right và tìm kiếm search thực hiện tìm kiếm chuỗi mẫu trong chuỗi văn bản. Phương thức search thực hiện một vòng lặp trên các vị trí có thể có của chuỗi văn bản và so sánh chuỗi mẫu với chuỗi con bắt đầu từ vị trí hiện tại. Nếu tìm thấy chuỗi mẫu, phương thức trả về vị trí đầu tiên của chuỗi mẫu trong chuỗi văn bản, ngược lại sẽ trả về -1.

Ở trong phần main, chúng ta khởi tạo đối tượng BoyerMoore với chuỗi mẫu và sau đó gọi phương thức search để tìm kiếm chuỗi mẫu trong chuỗi văn bản. Nếu phương thức search trả về -1 thì sẽ hiển thị thông báo “Pattern not found”, ngược lại sẽ hiển thị thông báo “Pattern found at index” và vị trí đầu tiên của chuỗi mẫu trong chuỗi văn bản.

8 thoughts on “Thuật toán Boyer-Moore trong Java”

  3. dobry sklep says:

    Hey! Do you know if they make any plugins to assist with Search Engine Optimization? I’m trying to
    get my blog to rank for some targeted keywords but I’m not
    seeing very good success. If you know of any please share.

    Many thanks! You can read similar blog here: E-commerce

    Trả lời

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *