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 Brute Force, Brute Force trong Java
Lần lượt xét từng vị trí i trong xâu ký tự gốc từ 0 đến n-m, so sánh y[i…(i+m-1)] với x[0…m-1] bằng cách xét từng cặp ký tự một và đưa ra kết quả tìm kiếm.
Đặc điểm:
- Thực hiện trái qua phải
- Không có pha tiền xử lí
- Độ phức tạp O(mn)
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 BruteForce { public static void search(char[] x, char[] y) { int m = x.length; int n = y.length; System.out.print("Các vị trí xuất hiện trong văn bản của xâu mẫu là: "); for (int j = 0; j <= n - m; j++) { for (int i = 0; i < m && x[i] == y[i + j]; i++) { if (i >= m - 1) { System.out.print(j + " "); } } } } public static void main(String[] args) { search("GCAGAGAG".toCharArray(), "GCATCGCAGAGAGTTATACAGTACG".toCharArray()); } }
Kiểm nghiệm thuật toán: