Алгоритм для нахождения самого маленького отрывка от поиска документа?

Из вопроса кажется, что вам даны позиции индекса для каждого из ваших n «поисковых слов» (word1, word2, word3, ..., word n ]) в документе. Используя алгоритм сортировки, n независимых массивов, связанных со словами поиска, можно легко представить в виде единого массива всех местоположений индексов в возрастающем числовом порядке и метки слова, связанной с каждым индексом в массиве (индекс множество).

Базовый алгоритм:

(Предназначен для работы независимо от того, предназначен ли плакат этого вопроса, чтобы позволить двум различным поисковым словам сосуществовать с одним и тем же индексным номером.)

Сначала мы определяем простую функцию для измерения длина фрагмента, содержащего все n меток, заданных в качестве начальной точки в массиве индексов. (Из определения нашего массива очевидно, что любая начальная точка в массиве обязательно будет индексированным местоположением одной из n меток поиска.) Функция просто отслеживает уникальные метки поиска, видимые как функция выполняет итерацию по элементам в массиве до тех пор, пока не будут соблюдены все n меток. Длина фрагмента определяется как разница между индексом последней найденной уникальной метки и индексом начальной точки в массиве индексов (первой найденной уникальной метки). Если все метки n не соблюдаются до конца массива, функция возвращает нулевое значение.

Теперь функцию длины фрагмента можно запустить для каждого элемента в массиве, чтобы связать размер фрагмента, содержащий все n слов для поиска, начиная с каждого элемента в массиве. Наименьшее ненулевое значение, возвращаемое функцией длины фрагмента по всему массиву индексов, - это фрагмент документа, который вы ищете.

Необходимые оптимизации:

1. Следите за значением текущей самой короткой длины фрагмента, чтобы значение было известно сразу после однократной итерации по массиву индексов.
2. При итерации по вашему массиву завершите функцию длины фрагмента, если текущий проверяемый фрагмент когда-либо превышает длину самого короткого фрагмента, который ранее наблюдался.
3. Когда функция длины фрагмента возвращает значение NULL, так как не удалось найти все n поисковых слов в оставшихся элементах массива индексов, свяжите длину фрагмента NULL со всеми последовательными элементами в массиве индексов.
4. Если функция длины фрагмента применяется к метке слова и метка, следующая сразу за ней, идентична начальной метке, присвойте нулевое значение начальной метке и переходите к следующей метке.

Вычислительная сложность:

Очевидно, что сортировочная часть алгоритма может быть организована за O ( n log n ).

Вот как я мог бы рассчитать временную сложность второй части алгоритма (любые критические замечания и исправления будут очень признательны).

В лучшем случае алгоритм применяет функцию длины фрагмента только к первому элементу в массиве индексов и обнаруживает, что фрагмента, содержащего все поисковые слова, не существует. Этот сценарий будет вычислен всего за n вычислений, где n - размер массива индексов. Немного хуже, если самый маленький фрагмент оказывается равным размеру всего массива. В этом случае вычислительная сложность будет немного меньше 2 n (один раз по массиву, чтобы найти наименьшую длину фрагмента, второй раз, чтобы продемонстрировать, что других фрагментов не существует). Чем короче средняя вычисленная длина фрагмента, тем больше раз нужно будет применить функцию длины фрагмента к массиву индексов. Мы можем предположить, что наш худший сценарий будет иметь место, когда функцию длины фрагмента нужно применить к каждому элементу в массиве индексов. Чтобы разработать случай, когда функция будет применяться к каждому элементу в массиве индексов, нам необходимо разработать массив индексов, в котором средняя длина фрагмента по всему массиву индексов незначительна по сравнению с размером массива индексов в целом. Используя этот случай, мы можем записать нашу вычислительную сложность как O (C n ), где C - некоторая константа, которая значительно меньше, чем n .Итоговая вычислительная сложность составляет:

O ( n log n + C n )

Где:

C << n

Редактировать:

AndreyT правильно указывает, что вместо сортировки слов, обозначенных в n log n времени, их можно было бы просто объединить (так как sub массивы уже отсортированы) в n log m время, где m - количество объединяемых массивов слов поиска. Это, очевидно, ускорит алгоритм в случаях, когда m < n .

Если я ничего не упустил, вот простой, O(n) алгоритм:

1. Представим фрагмент через (x, y), где x и y - начало и конец фрагмента соответственно.
2. Фрагмент является выполнимым, если он содержит все 3 поисковых слова.
3. Начнем с неосуществимого фрагмента (0,0).
4. Повторяем следующие действия, пока y не достигнет конца строки:
   5. Если текущий фрагмент (x, y) является выполнимым, переходим к фрагменту (x+1, y)
      Иначе (текущий фрагмент невыполним) переходим к фрагменту (x, y+1)
5. Выбираем самый короткий фрагмент из всех выполнимых фрагментов, через которые мы прошли.

Время работы - на каждой итерации либо x, либо y увеличивается на 1, очевидно, что x не может превышать y, а y не может превышать длину строки, поэтому общее количество итераций равно O(n). Кроме того, в этом случае выполнимость может быть проверена за O(1), поскольку мы можем отследить, сколько повторений каждого слова находится в текущем фрагменте. Мы можем поддерживать этот счет на уровне O(1) при каждом увеличении x или y на 1.

Корректность - Для каждого x мы вычисляем минимальный выполнимый фрагмент (x, ?). Таким образом, мы должны перейти к минимальному фрагменту. Также, если y - наименьший y такой, что (x, y) выполним, то если (x+1, y') - выполнимый фрагмент y' >= y (Именно поэтому данный алгоритм является линейным, а другие - нет).