Thuật toán tìm kiếm chuỗi

Question

Đối với hai thuật toán tìm kiếm chuỗi: KMP và cây hậu tố, được ưu tiên trong trường hợp nào? Đưa ra một số ví dụ thực tế.

Answer 1

cây Một hậu tố là tốt hơn nếu bạn sẽ phải trả lời rất nhiều câu hỏi như "là món quà kim trong Haystack?". KMP tốt hơn nếu bạn chỉ phải tìm kiếm một chuỗi trong một chuỗi khác và không phải thực hiện nhiều lần.

Một cây hậu tố là một cấu trúc dữ liệu tổng quát hơn nhiều, vì vậy bạn có thể làm nhiều hơn với nó. Xem những gì bạn có thể làm với nó here. KMP rất hữu ích cho việc tìm kiếm nếu một chuỗi là một chuỗi con trong chuỗi khác.

Bạn cũng có thể muốn kiểm tra các thuật toán khác, chẳng hạn như Boyer-Moore, Rabin-Karp và thậm chí cả thuật toán ngây thơ, vì có các trường hợp (đầu vào) trong đó một trường hợp tốt hơn so với các thuật toán khác.

Điểm mấu chốt là:

1. Nếu bạn có rất nhiều thắc mắc như một tôi đã đề cập ở trên, nó có giá trị để xây dựng một cây hậu tố và sau đó trả lời mỗi truy vấn nhanh hơn.
2. Nếu bạn cần làm nhiều hơn các loại truy vấn đó, cây hậu tố cũng đáng để xây dựng.
3. Nếu bạn chỉ quan tâm đến việc thỉnh thoảng tìm xem chuỗi có phải là chuỗi con của chuỗi khác không, sau đó sử dụng KMP.