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 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 TunedBoyerMoore {
  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 shift = preBc[x[m - 1]];
    preBc[x[m - 1]] = 0;
    int i = 0;
    int k = 0;

    while (i <= n - m) {
      k = preBc[y[i + m - 1]];
      while (k != 0) {
        i += k;
        k = preBc[y[i + m - 1]];
        i += k;
        k = preBc[y[i + m - 1]];
        i += k;
        k = preBc[y[i + m - 1]];
      }
      if (cmp(x, y, i)) {
        System.out.println(i);
      }
      i += shift;
    }
  }

  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 void main(String[] args) {
    char[] x = "GCAGAGAG".toCharArray();
    char[] y = "GCATCGCAGAGAGTATACAGTACG".toCharArray();
    System.out.print("Các vị trí xuất hiện trong văn bản của xâu mẫu là: ");
    search(x, y);
  }
}

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