Thuật toán tìm kiếm Morris Pratt

Posted on by cuongth

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 Morris Pratt, cài đặt bằng Java

Thuật toán tìm kiếm Morris Pratt

Đặ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)
– Thực hiện nhiều nhất 2n-1 các so sánh kí tự trong văn bản trong pha
tìm kiếm.
– Độ trễ bị bao bọc bởi m.
– Morris pratt là một phân tích chặt chẽ của thuật toán Brute force, đặc
biệt là với phương pháp này đã sử dụng các thông tin thu thập đc
trong quá trình quét văn bản.
– Nhược điểm của phương pháp Brute force là chúng ta phải tốn công so sánh lại
những kí tự trước đó.

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 MorrisPratt {
  // tim kiem cac vi tri cua x trong y
  // m: là vị trí tương ứng trên y bắt đầu 1 phép so sánh với x

  // mpNext[i] duoc dinh nghi la so phan tu quay nguoc lai de so sanh
  // ke tu vi tri i tren y khi ma y[m+i] khong khop voi x[i]
  public static int[] preMP(char[] x) {
    int[] mpNext = new int[x.length + 1];
    int i = 0;
    int j = mpNext[0] = -1;
    while (i < x.length) {
      while (j > -1 && (x[i] != x[j])) {
        j = mpNext[j];
      }
      mpNext[++i] = ++j;
    }
    return mpNext;
  }

  public static void search(char[] x, char[] y) {
    int[] mpNext = preMP(x);
    int i = 0;// the position of character in x
    int m = 0;// the beginning of the current match in y
    System.out.println("Các vị trí xuất hiện của x trong y là: ");
    while (m <= y.length - x.length) {
      if (x[i] == y[m + i]) {
        i++;

        if (i == x.length) {
          System.out.print(m + "    ");
          m = m + i - mpNext[i];
          i = 0;
        }
      } else {
        m = m + i - mpNext[i];
        if (i > 0) {
          i = mpNext[i];
        }
      }

    }
  }

  public static void main(String[] args) {
    String x = "GCAGAGAG";
    char[] X = x.toCharArray();
    String y = "GCATCGCAGAGAGTATACAGTACG";
    char[] Y = y.toCharArray();

    search(X, Y);
  }
}

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

Thuật toán tìm kiếm Morris Pratt, cài đặt bằng Java

stackjava.com