Chuỗi (String)

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 5)

Chuỗi (String)

Boyer-Moore Algorithm

Thời gian (Time) O(n / m)
Không gian (Space) O(sigma)

Mô tả nguyên lý

Thuật toán tìm kiếm chuỗi cực nhanh bằng cách duyệt từ phải sang trái.

Cài đặt mẫu (Implementation)

// Sử dụng bảng dịch chuyển ký tự xấu (Bad Character Heuristic).
Chuỗi (String)

KMP Pattern Searching

Thời gian (Time) O(n + m)
Không gian (Space) O(m)

Mô tả nguyên lý

Tìm kiếm chuỗi con (Pattern Matching) hiệu quả bằng bảng tiền tố LPS (Longest Prefix Suffix).

Cài đặt mẫu (Implementation)

// Sử dụng mảng tiền tố để tránh quay lui các ký tự đã khớp.
Chuỗi (String)

Rabin-Karp String Matching

Thời gian (Time) O(n + m) trung bình
Không gian (Space) O(1)

Mô tả nguyên lý

Thuật toán tìm kiếm chuỗi sử dụng kỹ thuật băm lăn (Rolling Hash).

Cài đặt mẫu (Implementation)

// Tính mã băm của chuỗi mẫu và so sánh trượt trên chuỗi chính.
Chuỗi (String)

Suffix Array Construction

Thời gian (Time) O(n log² n)
Không gian (Space) O(n)

Mô tả nguyên lý

Tập hợp tất cả các hậu tố của chuỗi được sắp xếp theo thứ tự từ điển.

Cài đặt mẫu (Implementation)

// Xây dựng mảng chỉ mục hậu tố hỗ trợ truy vấn chuỗi cực nhanh.
Chuỗi (String)

Z-Algorithm

Thời gian (Time) O(n + m)
Không gian (Space) O(n + m)

Mô tả nguyên lý

Tính mảng Z để tìm kiếm chuỗi con xuất hiện trong văn bản.

Cài đặt mẫu (Implementation)

// Tạo mảng Z lưu độ dài chuỗi con chung dài nhất bắt đầu từ mỗi vị trí so với xâu gốc.