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: