Tôi đã xuất hiện trong một cuộc phỏng vấn nơi tôi được yêu cầu viết một thuật toán cho băm khóa một phần, tức là; nếu ABCBC được chèn vào trong băm thì tìm kiếm bất kỳ chuỗi con nào sẽ trả về giá trị được lưu trữ. Câu trả lời của tôi là tạo một tập hợp tất cả các phần có thể có của một khóa đã cho và duy trì một ánh xạ giữa mỗi chuỗi con đến một hoặc nhiều chuỗi gốc của nó. Sau đó, duy trì một BST của bộ sưu tập của tất cả các chất nền. Mỗi nút sẽ trỏ đến một tập hợp các giá trị thực tế mà chuỗi con có thể khớp với. Ví dụ: A, AB, ABC, ABCB, ABCBC, B, BC, BCB, BCBC, C, CB, CBC là các chất nền có thể cho chuỗi này. Có thể có các chuỗi khác cũng giống như BAB trong đó, AB và B là chuỗi con của. Vì vậy, cho AB, nó sẽ ánh xạ tới hai chuỗi BAB và ABCBC.Cách tốt nhất để thực hiện bẻ khóa một phần
Có cách nào khác hiệu quả hơn không? Cảm ơn
Bạn có thể lưu trữ các nút con trong một hashtable (băm trên giá trị chuỗi con, rõ ràng). Điều này sẽ cắt tìm kiếm của bạn từ O (log n) thành O (1). Độ phức tạp của không gian có thể so sánh hoặc hơi tệ hơn (do các khe trống trong bảng). – jpm
Dường như việc tạo băm cho mỗi chuỗi con có thể trở nên không khả thi ... có lẽ có một mẹo khác đang diễn ra ở đây? Bất cứ điều gì có thể sử dụng với cây tiền tố? –
Cây Suffix (http://en.wikipedia.org/wiki/Suffix_tree) có lẽ, mặc dù nó không thực sự "băm". Tôi không thực sự hiểu làm thế nào các bộ sưu tập tổng thể hoạt động: giả sử tôi chèn ABCBC với một giá trị của 4. Sau đó, tìm kiếm ABC trả về 4, đủ công bằng. Điều gì xảy ra nếu tôi cũng chèn CDABC với giá trị là 5. Bây giờ, tìm kiếm ABC trả về cái gì? Bạn không thể nói "nên trả về giá trị được lưu trữ" và cũng nói, "nó sẽ ánh xạ tới hai chuỗi", bởi vì nó không thể làm cả hai. –