Оптимальное время выполнения для простой схемы сжатия

Question

Вот простая головоломка с некоторыми приложениями в биоинформатике. Это абстрактная версия чего-то, что появилось на работе у друга.

Рассмотрим очень простую схему сжатия, вывод которой состоит из потока двух операций:

• put(a): выводит символ a
• dup(): дублирует весь вывод, написанный до сих пор

Для удобства записи напишите сам символ x для put('x') и * для dup().

Например, "a**b*c" расширяется до "aaaabaaaabc".

Чтобы сжать заданную строку s, найдите кратчайший список этих двух операций для ее генерации.

Например, для "aaaaaaaaaab" сокращается до a**a*b. (a***aab также возможно, но на один символ длиннее.)

Мой вопрос: какова наилучшая достижимая среда выполнения для оптимального сжатия? (И каков алгоритм, который достигает того времени выполнения.)

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

Answer 1

Да, для этой схемы сжатия возможно линейное время выполнения.

Создать список dp.Элемент ih этого списка будет наилучшим возможным сжатием для первых i элементов строки.

dp[1] = 1
dp[i] = dp[i-1] + 1
if i is even and first i/2 elements of string are equal to second i/2 elements:
    dp[i] = min(dp[i], dp[i/2] + 1)

Чтобы проверить, равны ли первые i/2 элементы вторым i/2 элементам, вы можетенайти самый длинный общий префикс между строкой и суффиксом, начиная с индекса i/2.Если этот префикс больше или равен i/2 по длине, то первые i/2 элементы действительно равны вторым i/2 элементам.

Ускорение этой операции возможно с использованием модифицированного массива LCP.

Сначала создайте массив суффиксов для строки в O(n).

Затем создайте самый длинный массив общих префиксов для суффикса.массив в O(n).

Теперь найдите индекс полной строки в массиве суффиксов.Допустим, это i.Теперь итерируйте от i до конца массива LCP, заменяя каждое значение минимальным, видимым до сих пор.Аналогичным образом, выполните итерацию вниз от i-1 до 0 в массиве LCP, заменив каждое значение минимальным, видимым до сих пор.

Как только это будет сделано, каждое значение в массиве LCP представляет самый длинный общий префикс этогосуффикс с полной строкой, который требуется алгоритму.Обратите внимание, что эти значения упорядочены в соответствии с отсортированными суффиксами, а не по позиции суффиксов в строке.Сопоставить это довольно просто, используя массив суффиксов.