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 Knuth Morris Pratt
Thuật toán tìm kiếm Knuth Morris Pratt (KMP)
Đặc điểm:
– Thực hiện phép so sánh từ trái sang phải
– Pha tiền xử lí có độ phức tạp về không gian và thời gian là O(m)
– Pha tìm kiếm có độ phức tạp về thời gian O(m+n)
– Knuth Morris Pratt là một phân tích chặt chẽ của thuật toán Morris
pratt.
– Bảng kmpNext giúp loại bỏ việc so sánh lại những kí tự đã so sánh
trước đó trong phương pháp thông thường.
– Thực hiện: Dò từ trái sang phải cho tới khi gặp vị trí X và Y không
giống nhau. Giả sử: X[i] != Y[j], xem giá trị kmpNext[i] tương ứng.
+) Nếu kmpNext[i] = -1 thì dịch chuỗi X lên một bước.
+) Nếu kmpNext[i] = m, >= 0 thì ta di chuyển X[m] trùng với i.
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 KnuthMorrisPratt {
public static int[] preKMP(char[] x) {
int[] kmpNext = new int[x.length + 1];
int i = 0;
int j = -1;
kmpNext[0] = -1;
while (i < x.length - 1) {
while (j > -1 && x[i] != x[j]) {
j = kmpNext[j];
}
i++;
j++;
if (x[i] == x[j]) {
kmpNext[i] = kmpNext[j];
} else {
kmpNext[i] = j;
}
}
return kmpNext;
}
public static void search(char[] x, char[] y) {
int[] kmpNext = preKMP(x);
int i = 0;// the position of character in x
int m = 0;// the beginning of the current match in y
while (m <= y.length - x.length) {
if (x[i] == y[m + i]) {
i++;
if (i == x.length) {
System.out.print(m + " ");
m = m + i - kmpNext[i];
i = kmpNext[i];
}
} else {
m = m + i - kmpNext[i];
i = 0;
}
}
}
public static void main(String[] args) {
String x = "GCAGAGAG";
char[] X = x.toCharArray();
String y = "GCATCGCAGAGAGTATACAGTACG";
char[] Y = y.toCharArray();
System.out.print("Các vị trí xuất hiện của x trong y là: ");
search(X, Y);
}
}