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, đối với chuỗi y[0..n-1] ta dùng 1 biến j để chốt ở phía đầu. G/s rằng trong quá trình so sánh ta gặp 1 mis-match tai vị trí x[i]=a của mẫu và y[i+j]=b trong khi đang thử khớp tại vị trí j. Phép dịch chuyển bad-character shift sẽ khớp kí tự y[i+j] với 1 ký tự (bên phải nhất) trong đoạn x[0..m-2]. Nếu y[i+j] không xuất hiện trong x, ta thấy ngay rằng không có xuất hiện nào của x trong y mà lại chứa chấp y[i+j], do đó ta có thể đặt cửa sổ ngay sau y[i+j], tức là y[j+i+1]

Đặ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= (y0, y1,…, yn-1) độ dài n

Ouput: tất cả các vị trí của x trong y

Cài đặt thuật toán:

public class Horspool {
  public static boolean cmp(char[] x, char[] y, int y1) {
    for (int i = 0; i < x.length; i++) {
      if (x[i] != y[y1++]) {
        return false;
      }
    }
    return true;
  }

  public static int[] preBc(char[] x) {
    int[] bc = new int[255];
    int m = x.length;
    for (int i = 0; i < 255; i++) {
      bc[i] = m;
    }
    for (int i = 0; i < m - 1; i++) {
      bc[(int) x[i]] = m - i - 1;
    }
    return bc;
  }

  public static void search(char[] x, char[] y) {
    int m = x.length;
    int n = y.length;
    int[] preBc = preBc(x);
    int i = 0;
    while (i <= n - m) {
      char c = y[i + m - 1];
      if (cmp(x, y, i)) {
        System.out.println("Các vị trí xuất hiện trong văn bản của xâu mẫu là: " + i);
      }
      i = i + preBc[c];

    }
  }

  public static void main(String[] args) {
    char[] x = "GCAGAGAG".toCharArray();
    char[] y = "GCATCGCAGAGAGTATACAGTACG".toCharArray();
    search(x, y);
  }
}

Kiểm nghiệm thuật toán: