Chuỗi (String)
Boyer-Moore Algorithm
ID: #38
Xem trên trang chủ
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
ID: #36
Xem trên trang chủ
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
ID: #37
Xem trên trang chủ
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
ID: #40
Xem trên trang chủ
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
ID: #39
Xem trên trang chủ
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.