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);
}
}