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);
  }
}

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