Cài đặt thuật toán Z trong lập trình

Thuật toán Z là một trong những thuật toán mạnh mẽ và hiệu quả nhất để xử lý các vấn đề liên quan đến chuỗi ký tự, đặc biệt trong việc tìm kiếm các mẫu con (substring) trong một chuỗi chính. Thuật toán này có thể chạy trong thời gian O(n + m), nơi n là độ dài của chuỗi chính và m là độ dài của mẫu con. Bằng cách tính toán "mảng Z" cho một chuỗi tổ hợp, thuật toán này có thể xác định nhanh chóng các vị trí trong chuỗi chính trùng khớp với mẫu con.

Giới thiệu về thuật toán Z

Thuật toán Z hoạt động bằng cách tạo ra một mảng Z cho một chuỗi tổ hợp (gồm mẫu con và chuỗi chính), trong đó mỗi phần tử tại vị trí i của mảng Z cho biết số ký tự khớp liên tiếp dài nhất bắt đầu từ vị trí i cho đến cuối chuỗi.

Các bước cài đặt thuật toán Z

Bước 1: Tạo chuỗi tổ hợp

Trước tiên, cần tạo một chuỗi tổ hợp bằng cách kết hợp mẫu con, một dấu phân cách đặc biệt (thường là ký tự không có trong mẫu hoặc chuỗi chính, chẳng hạn như '$'), và chuỗi chính.

pattern = "maucon"
text = "chuoinhuanhuichuoinhuamauchinh"
concat = pattern + "$" + text

Bước 2: Tính toán mảng Z cho chuỗi kết hợp

Mảng Z sẽ được tính toán cho chuỗi tổ hợp này. Mỗi chỉ số i của mảng Z sẽ chứa số ký tự khớp liên tiếp dài nhất từ vị trí i trong chuỗi tổ hợp.

def calculate_z(concat):
    n = len(concat)
    Z = [0] * n
    L, R, K = 0, 0, 0
    for i in range(1, n):
        if i > R:
            L, R = i, i
            while R < n and concat[R] == concat[R - L]:
                R += 1
            Z[i] = R - L
            R -= 1
        else:
            K = i - L
            if Z[K] < R - i + 1:
                Z[i] = Z[K]
            else:
                L = i
                while R < n and concat[R] == concat[R - L]:
                    R += 1
                Z[i] = R - L
                R -= 1
    return Z

concat_z = calculate_z(concat)

Bước 3: Duyệt qua mảng Z để tìm các vị trí khớp

Sau khi tính toán xong mảng Z, cần kiểm tra các giá trị của mảng này để xác định các vị trí trong chuỗi chính nơi mẫu con xuất hiện. Giá trị lý tưởng trong mảng Z mà chúng ta tìm kiếm sẽ là độ dài của mẫu con.

def search_pattern(pattern, text):
    concat = pattern + "$" + text
    Z = calculate_z(concat)
    pattern_length = len(pattern)
    result = []
    
    for i in range(len(Z)):
        if Z[i] == pattern_length:
            result.append(i - pattern_length - 1)
    
    return result

result = search_pattern("maucon", "chuoinhuanhuichuoinhuamauchinh")

print("Pattern found at indices: ", result)

Ưu điểm của thuật toán Z

1. Độ phức tạp thời gian: Thuật toán Z hoạt động trong thời gian tuyến tính O(n + m), rất hiệu quả ngay cả với các chuỗi dài.
2. Đơn giản: Thuật toán này dễ hiểu và dễ triển khai, cần ít không gian bộ nhớ phụ trợ so với nhiều thuật toán tìm kiếm chuỗi khác.
3. Linh hoạt: Có thể ứng dụng vào nhiều bài toán khác nhau trong lập trình, như tìm kiếm mẫu, phát hiện đoạn lặp, và nhiều ứng dụng khác trong xử lý chuỗi.

Thuật toán Z là một công cụ mạnh mẽ mà mỗi lập trình viên nên làm quen, đặc biệt khi làm việc với các chuỗi ký tự. Việc hiểu và triển khai thuật toán này không chỉ giúp giải quyết các bài toán tìm kiếm chuỗi hiệu quả hơn, mà còn mở ra nhiều cách tiếp cận sáng tạo cho các vấn đề phức tạp khác trong lập trình.