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 Not So Naive.

Thuật toán tìm kiếm Not So Naive

Cải tiến từ Brute Force, khi x so khớp với y nằm trong khoảng [j..j+m-1]. Nếu x[0]=x[1] và x[1]<>y[j+1]  hoặc x[0]<>x[1] và x[1]=y[j+1] thì dịch chuyển sang phải 2 vị trí, các trường hợp còn lại dịch chuyển một vị trí

Đặc điểm:

• Pha tiền xử lí có độc phức tạp là hằng số
• Độ phức tạp của thuật toán mà 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 NotSoNaive {
  
  public static boolean cmp(char[] x, char[] y) {
    if (x.length != y.length)
      return false;
    for (int i = 0; i < x.length; i++) {
      if (x[i] != y[i]) {
        return false;
      }
    }
    return true;
  }

  public static void search(char[] x, char[] y) {
    int k = 1;
    int l = 2;
    char[] x1 = Arrays.copyOfRange(x, 2, x.length);
    if (x[0] == x[1]) {
      k = 2;
      l = 1;
    }
    int i = 0;

    while (i <= y.length - x.length) {
      if (x[1] != y[i + 1]) {
        i = i + k;
      } else {
        if (x[0] == y[i] && cmp(x1, Arrays.copyOfRange(y, i + 2, i + x.length))) {
          System.out.print(i + "    ");
        }
        i += l;
      }
    }

  }

  public static void main(String[] args) {
    char[] x = "GCAGAGAG".toCharArray();
    char[] y = "GCATCGCAGAGAGTATACAGTACG".toCharArray();
    System.out.println("Các vị trí xuất hiện trong văn bản của xâu mẫu là: ");
    search(x, y);
  }
}

Kiểm nghiệm thuật toán: