A панорамное окно - это подстрока большого фрагмента текста, содержащего все 26 букв алфавита.Чтобы процитировать пример из Википедии, с учетом этого текста:
Я пел, и думал, что я пел очень хорошо;но он просто посмотрел мне в лицо с очень насмешливым выражением и сказал: «Как давно вы поете, мадемуазель?»
Наименьшее панграмматическое окно в тексте - это строка:
г очень хорошо;но он просто посмотрел мне в лицо с очень насмешливым бывшим
, который действительно содержит каждую букву хотя бы один раз.
Мой вопрос таков: Учитывая текстовый корпус,Каков наиболее эффективный алгоритм поиска наименьшего панграмматического окна в тексте?
Я уже обдумал это и уже предложил следующие алгоритмы.У меня есть сильное чувство, что они не оптимальны, но я подумал, что опубликую их в качестве отправной точки.
Существует простой наивный алгоритм, который работает во времени O (n 2 ) и пробел O (1): для каждой позиции в строке отсканируйте вперед от этой позиции и проследите, какие буквы вы видели (возможно, в битовом векторе, который, поскольку имеется только 26 различных букв, занимает пробел O (1).)).Как только вы нашли все 26 букв, у вас есть длина самого короткого панграмматического окна, начиная с этой заданной точки.Каждое сканирование может занять время O (n), и есть O (n) сканирования, в общей сложности O (n 2 ) времени.
Мы также можем решить эту проблему ввремя O (n log n) и пространство O (n) с использованием модифицированного двоичного поиска.Создайте 26 массивов, по одному на каждую букву алфавита, затем заполните эти массивы позициями каждой буквы во входном тексте в отсортированном порядке.Мы можем сделать это, просто просматривая текст, добавляя каждый индекс в массив, соответствующий текущему символу.Получив это, мы можем найти за время O (log n) длину самого короткого панграмматического окна, начинающегося с некоторого индекса, выполнив 26 двоичных поисков в массивах, чтобы найти самое раннее время, когда каждый символ появляется во входном массиве вили после данного индекса.Какое бы из этих чисел ни было наибольшее, оно дает символ «длинный полюс», который появляется дальше всего вниз по цепочке, и, таким образом, дает конечную точку панграмматического окна.Выполнение этого шага поиска занимает O (log n) времени, и, поскольку мы должны сделать это для всех n символов в строке, общее время выполнения составляет O (n log n) с использованием O (n) памяти для массивов.
Еще одним уточнением вышеупомянутого подхода является замена массивов и двоичного поиска на деревьев Ван Эмде Боаса и поиск предшествующего уровня.Это увеличивает время создания до O (n log log n), но сокращает каждое время поиска до O (log log n), для чистого времени выполнения O (n log log n) при использовании O (n) места.
Есть ли лучшие алгоритмы?