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 sánh tiếp 2 kí tự giữa rồi đến 2 kí tự cuối tương ứng của 2 mảng trước

Đặ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)

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

public class Raita {
  public static boolean cmp(char[] x, int x1, int x2, char[] y, int y1) {
    for (int i = x1; i <= x2; 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];
      char first = x[0];
      char middle = x[m / 2];
      char last = x[m - 1];
      if (first == y[i] && middle == y[i + m / 2] && last == y[i + m - 1] && cmp(x, 1, m - 2, y, i + 1)) {
        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: