Câu hỏi phỏng vấn Strings
Câu hỏi

Giải thích thuật toán Boyer-Moore và cung cấp ví dụ?

Câu trả lời

Thuật toán Boyer-Moore:

Thuật toán Boyer-Moore là một thuật toán tìm kiếm chuỗi hiệu quả trong văn bản. Nó sử dụng hai cơ chế quan trọng để tối ưu hóa việc tìm kiếm:

  1. Bad character rule: Quy tắc ký tự xấu: Di chuyển cửa sổ tìm kiếm theo hướng từ phải sang trái của mẫu. Nếu ký tự không khớp, di chuyển cửa sổ sang phải để căn chỉnh với ký tự không khớp trong văn bản dựa trên bảng tần suất xuất hiện của ký tự không khớp trong mẫu.

  2. Good suffix rule: Quy tắc hậu tố tốt: Khi phần đuôi của mẫu khớp với văn bản, di chuyển cửa sổ tìm kiếm đến khi có sự không khớp. Thuật toán sẽ di chuyển dựa trên một bảng lưu trữ thông tin về các chuỗi con hậu tố khớp với phần đuôi của mẫu.

Ví dụ:

G...

senior

senior

Gợi ý câu hỏi phỏng vấn

expert

So sánh StringsRopes từ phân tích hiệu suất?

expert

Khi nào nên sử dụng Ropes thay vì StringBuilders?

senior

Nêu một số hạn chế của Ropes?

Bình luận

Chưa có bình luận nào

Chưa có bình luận nào