Thuật toán KMP (Knuth-Morris-Pratt) là một thuật toán tìm kiếm chuỗi hiệu quả được sử dụng để tìm kiếm một chuỗi con trong một chuỗi lớn hơn. Thuật toán này dựa trên việc xây dựng một bảng tiền tố (prefix table) để giảm thiểu số lần so sánh trong quá trình tìm kiếm.
Dưới đây là mã Java thực hiện thuật toán KMP:
public static int[] buildPrefixTable(String pattern) {
int[] prefixTable = new int[pattern.length()];
int i = 0;
int j = 1;
while (j < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(j)) {
prefixTable[j] = i + 1;
i++;
j++;
} else {
if (i == 0) {
prefixTable[j] = 0;
j++;
} else {
i = prefixTable[i - 1];
}
}
}
return prefixTable;
}
public static List<Integer> searchPattern(String text, String pattern) {
List<Integer> matches = new ArrayList<>();
int[] prefixTable = buildPrefixTable(pattern);
int i = 0;
int j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
}
if (j == pattern.length()) {
matches.add(i - j);
j = prefixTable[j - 1];
} else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
if (j == 0) {
i++;
} else {
j = prefixTable[j - 1];
}
}
}
return matches;
}
Trong đó, hàm buildPrefixTable nhận vào chuỗi pattern và trả về bảng tiền tố tương ứng. Hàm searchPattern nhận vào hai chuỗi text và pattern và trả về một danh sách các vị trí bắt đầu của chuỗi con pattern trong chuỗi text.
Thuật toán KMP được thực hiện bằng cách duyệt qua chuỗi pattern và xây dựng bảng tiền tố. Sau đó, ta duyệt qua chuỗi text và so sánh các ký tự với chuỗi pattern để tìm kiếm chuỗi con. Nếu có ký tự không khớp, ta sử dụng bảng tiền tố để quay lại vị trí trước đó để tiếp tục tìm kiếm.
Tuy nhiên, độ phức tạp của thuật toán KMP là O(m + n), trong đó m và n lần lượt là độ dài của chuỗi con và chuỗi lơn hơn. Vì vậy, thuật toán này rất hiệu quả cho các tác vụ tìm kiếm chuỗi trong văn bản lớn.