A pangrammatic window là chuỗi con của một đoạn văn bản lớn hơn chứa tất cả 26 chữ cái trong bảng chữ cái. Để trích dẫn một ví dụ từ Wikipedia, cho văn bản này:Thuật toán hiệu quả để tìm cửa sổ pangrammatic nhỏ nhất?
Tôi đã hát và nghĩ rằng tôi đã hát rất tốt; nhưng anh ấy chỉ nhìn lên khuôn mặt của tôi với một biểu hiện rất khó hiểu, và nói, "Bạn đã hát bao lâu rồi, Mademoiselle?"
Cửa sổ pangrammatic nhỏ nhất trong văn bản là chuỗi này:
g rất tốt; nhưng anh ta chỉ nhìn lên khuôn mặt của tôi với một chữ rất khó xử
Thực sự chứa mọi chữ cái ít nhất một lần.
Câu hỏi của tôi là: Với văn bản văn bản, thuật toán hiệu quả nhất để tìm cửa sổ pangrammatic nhỏ nhất trong văn bản là gì?
Tôi đã đưa ra một số suy nghĩ này và đưa ra các thuật toán sau đây. Tôi có một cảm giác mạnh mẽ rằng đây không phải là tối ưu, nhưng tôi nghĩ rằng tôi muốn đăng chúng như là một điểm khởi đầu.
Có một thuật toán ngây thơ đơn giản chạy trong thời gian O (n) và không gian O (1): Đối với mỗi vị trí trong chuỗi, quét về phía trước từ vị trí đó và theo dõi những chữ cái bạn đã xem trong một bit bit, trong đó, vì chỉ có 26 chữ cái khác nhau, lấy không gian O (1)). Một khi bạn đã tìm thấy tất cả 26 chữ cái, bạn có chiều dài của cửa sổ pangrammatic ngắn nhất bắt đầu từ điểm đã cho. Mỗi lần quét có thể mất thời gian O (n), và có O (n) quét, với tổng thời gian O (n).
Chúng tôi cũng có thể giải quyết vấn đề này trong thời gian O (n log n) và không gian O (n) bằng cách sử dụng tìm kiếm nhị phân đã sửa đổi. Xây dựng 26 mảng, một cho mỗi chữ cái của bảng chữ cái, sau đó điền các mảng đó với vị trí của mỗi chữ cái trong văn bản đầu vào theo thứ tự sắp xếp. Chúng ta có thể thực hiện điều này bằng cách quét qua văn bản, thêm mỗi chỉ mục vào mảng tương ứng với ký tự hiện tại. Khi chúng ta có điều này, chúng ta có thể tìm thấy, trong thời gian O (log n), chiều dài của cửa sổ pangrammatic ngắn nhất bắt đầu từ một số chỉ mục bằng cách chạy 26 tìm kiếm nhị phân trong mảng để tìm thời gian sớm nhất mà mỗi ký tự xuất hiện trong mảng đầu vào hoặc sau chỉ mục đã cho. Cho dù số nào trong số này là lớn nhất thì nhân vật "cực dài" xuất hiện xa nhất trong chuỗi, và do đó cung cấp cho điểm cuối của cửa sổ pangrammatic. Chạy bước tìm kiếm này có thời gian O (log n) và vì chúng ta phải thực hiện nó cho tất cả n ký tự trong chuỗi, tổng thời gian chạy là O (n log n), với việc sử dụng bộ nhớ O (n) cho các mảng.
Tinh chỉnh thêm cho phương pháp trên là thay thế mảng và tìm kiếm nhị phân bằng van Emde Boas trees và tìm kiếm tiền thân. Điều này làm tăng thời gian tạo thành O (n log log n), nhưng giảm mỗi lần tìm kiếm thành thời gian O (log log n), cho thời gian thực của O (n log log n) với O (n) không gian sử dụng.
Có bất kỳ thuật toán nào tốt hơn không?
Tôi khá chắc chắn điều này hoạt động, nhưng tôi không chắc chắn tôi thấy lý do tại sao điều này sẽ không vô tình bỏ qua một cửa sổ bằng cách nào đó. Bạn có chắc chắn rằng điều này sẽ xem xét chính xác tất cả các cửa sổ? – templatetypedef
@templatetypedef, Bằng chứng rất dễ. Bất biến của bước 2 là một thực tế là độ dài của cửa sổ pangrammatic ngắn nhất bắt đầu từ iterator thứ hai là chính xác (iterator đầu tiên - iterator thứ hai) bởi vì giảm lần đầu tiên iterator loại bỏ một trong các ký tự từ tập hợp. Vì vậy, bạn có thể coi thuật toán này là biến thể tối ưu hóa của thuật toán n^2. –
Làm thế nào là O (N), và làm thế nào nó không phụ thuộc vào kích thước bảng chữ cái M? Cụ thể, làm cách nào bạn thực hiện việc kiểm tra "Dừng khi tất cả 26 bộ đếm không khác." trong O (1), (kể từ khi nó liên tục, nó có thể được thực hiện trong O (1) nhưng đối với trường hợp chung của M?) – kolistivra