Tìm tất cả (từ tiếng Anh) chất nền của một chuỗi đã cho

Question

Đây là một cuộc phỏng vấn question: Tìm tất cả (từ tiếng Anh) chất nền của một chuỗi nhất định. (every = every, ever, very).

Rõ ràng, chúng ta có thể lặp qua tất cả các chất nền và kiểm tra từng chất chống lại một từ điển tiếng Anh, được tổ chức như một bộ. Tôi tin rằng từ điển đủ nhỏ để phù hợp với RAM. Cách sắp xếp từ điển? Đối với như tôi nhớ, lệnh spell gốc đã tải tệp words trong một bitmap, đại diện cho một tập hợp các giá trị băm từ. Tôi sẽ bắt đầu từ đó.

Một giải pháp khác là một trie được tạo từ từ điển. Sử dụng trie chúng ta có thể lặp qua tất cả các ký tự chuỗi và kiểm tra trie cho mỗi ký tự. Tôi đoán sự phức tạp của giải pháp này sẽ giống nhau trong trường hợp xấu nhất (O(n^2))

Có hợp lý không? Bạn có đề xuất các giải pháp khác không?

Answer 1

Tôi không chắc Trie sẽ hoạt động dễ dàng để khớp các từ phụ bắt đầu ở giữa chuỗi hay không.

Một giải pháp khác có khái niệm tương tự là sử dụng máy trạng thái hoặc cụm từ thông dụng. cụm từ thông dụng chỉ là word1 | word2 | .... Tôi không chắc liệu các công cụ biểu thức thông thường có thể xử lý một cụm từ bao gồm toàn bộ ngôn ngữ tiếng Anh hay không, nhưng không khó để xây dựng máy trạng thái tương đương từ điển.

Khi biểu thức chính quy được biên dịch \ máy nhà nước được xây dựng sự phức tạp của việc phân tích một chuỗi cụ thể là O (n)

Answer 2

Các giải pháp đầu tiên có thể được tinh chế để có một bản đồ băm khác nhau cho mỗi chiều dài từ (để giảm va chạm) nhưng khác hơn là tôi không thể nghĩ ra bất cứ điều gì tốt hơn đáng kể.

Answer 3

Aho-Corasick string matching algorithm "xây dựng một máy trạng thái hữu hạn giống như một bộ ba với các liên kết bổ sung giữa các nút nội bộ khác nhau."
Nhưng mọi thứ được coi là "xây dựng một trie từ từ điển tiếng Anh và thực hiện tìm kiếm đồng thời trên tất cả các hậu tố của chuỗi đã cho" nên khá tốt cho một cuộc phỏng vấn.