Thuật toán tìm kiếm Smith

Posted on by cuongth

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:

+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 Smith {
  public static int[] preQsBc(char[] x) {
    int[] bc = new int[255];
    int m = x.length;
    for (int i = 0; i < 255; i++) {
      bc[i] = m + 1;
    }
    for (int i = 0; i < m; i++) {
      bc[(int) x[i]] = m - i;
    }
    return bc;
  }

  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[] preQsBc = preQsBc(x);
    int i = 0;
    while (i <= n - m) {
      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 += Math.max(preBc[y[i + m - 1]], preQsBc[y[i + m]]);
    }
  }

  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();
    search(x, y);
  }
}

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

Thuật toán tìm kiếm Smith, cài đặt Smith bằng Java

stackjava.com