O (n ^ 2) (или O (n ^ 2lg (n))?) Алгоритм для вычисления самой длинной общей подпоследовательности (LCS) из двух «кольцевых» строк

Question

Эта проблема возникла на сегодняшнем соревновании по программированию в Тихоокеанском регионе, в ходе которого никто не решил ее.Это проблема B, и полный набор проблем находится здесь: http://www.acmicpc -pacnw.org / icpc-statements-2011.zip .Существует известный алгоритм O (n ^ 2) для LCS двух строк с использованием динамического программирования.Но когда эти строки распространяются на кольца, я понятия не имею ...

PS обратите внимание, что это подпоследовательность, а не подстрока, поэтому элементы не должны быть смежными друг с другом

PSЭто может быть не O (n ^ 2), а O (n ^ 2lgn) или что-то, что может дать результат за 5 секунд на обычном компьютере.

Answer 1

Поиск в Интернете, по-видимому, охватывается разделом 4.3 статьи «Сравнение последовательных строк» ​​Ландау, Майерса и Шмидта по цене O (ne)

Answer 2

В качестве продолжения ответа Макдовеллы я хотел бы отметить, что решение O (n ^ 2 lg n), представленное в статье Мэйса, является предполагаемым решением проблемы конкурса (отметьте http://www.acmicpc - pacnw.org/ProblemSet/2011/solutions.zip). Решение O (ne) в статье Ландау и др. НЕ применимо к этой проблеме, так как этот документ нацелен на расстояние редактирования, а не LCS. В частности, решение для циклического редактирования расстояния применяется только в том случае, если все операции редактирования (добавление, удаление, замена) имеют стоимость единицы (1, 1, 1). LCS, с другой стороны, эквивалентно редактированию расстояний с (добавить, удалить, заменить) затратами (1, 1, 2). Они не эквивалентны друг другу; например, рассмотрим входные строки «ABC» и «CXY» (для ациклического случая вы можете создать циклические контрпримеры аналогично). LCS этих двух строк - «C», но минимальное изменение стоимости за единицу - замена каждого символа по очереди.

В 110 строках, но без сложных структур данных, решение Maes подходит к верхнему пределу того, что разумно реализовать в условиях конкурса. Даже если решение Ландау и его коллег может быть адаптировано для обработки циклических LCS, сложность структуры данных делает ее невозможной в условиях конкурса.

И последнее, но не менее важное: я хотел бы отметить, что решение O (n ^ 2) существует для CLCS, описанное здесь: http://arxiv.org/abs/1208.0396 В 60 строках нет сложных структур данных и только 2 Это решение вполне разумно реализовать в условиях конкурса. Однако достижение решения может быть другим.

Answer 3

Хорошая идея - «удвоить» строки и применить стандартный алгоритм динамического программирования. Проблема в том, что для получения оптимальной циклической LCS необходимо «запустить алгоритм из нескольких начальных условий». Только одно начальное условие (например, установка всех переменных Lij на 0 на границах) в общем случае не подойдет. На практике выясняется, что число необходимых начальных состояний равно O (N) (они охватывают диагональ), поэтому мы возвращаемся к алгоритму O (N ^ 3). Тем не менее, этот подход обладает некоторыми достоинствами, поскольку его можно использовать для разработки эффективных O (N ^ 2) эвристик (не точных, но почти точных) для CLCS.

Я не знаю, существует ли истинный O (N ^ 2), и было бы очень интересно, если бы кто-то его знал. Проблема CLCS имеет довольно интересные свойства "периодичности": длина CLCS p-количество повторных строк - это p-кратный CLCS строк. Это можно доказать, приняв геометрическое представление о проблеме.

Кроме того, есть некоторые дополнительные преимущества этой проблемы: можно показать, что если Lc (N) обозначает усредненное значение длины CLCS двух случайных строк длины N, то | Lc (N) -CN | O (\ sqrt {N}), где C - постоянная Хватала-Санкова. Для усредненной длины L (N) стандартной LCS единственный результат скорости, о котором я знаю, говорит, что | L (N) -CN | является O (sqrt (Nlog N)). Может быть хороший способ сравнить Lc (N) с L (N), но я этого не знаю.

Другой вопрос: ясно, что длина CLCS не является сверхаддитивной, в отличие от длины LCS. Под этим я подразумеваю, что это неправда, что CLCS (X1X2, Y1Y2) всегда больше, чем CLCS (X1, Y1) + CLCS (X2, Y2) (очень легко найти контрпримеры с помощью компьютера). Но кажется возможным, что усредненная длина Lc (N) сверхаддитивна (Lc (N1 + N2) больше, чем Lc (N1) + Lc (N2)) - хотя, если есть доказательство, я его не знаю. Один скромный интерес в этом вопросе состоит в том, что значения Lc (N) / N для первых нескольких значений N будут тогда обеспечивать хорошие границы для постоянной Чватала-Санкоффа (намного лучше, чем L (N) / N).

Answer 4

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