Информатика · объяснение и практика
Чем общая подпоследовательность отличается от общего подотрезка строки
Сравниваем две строки, различаем непрерывный фрагмент и сохранённый порядок символов, затем строим состояния динамического программирования.

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
Общая подпоследовательность получается удалением символов из обеих строк без перестановки оставшихся. Её символы не обязаны стоять рядом. Общая подстрока, напротив, должна быть непрерывным фрагментом каждой строки.
Пропускать разрешено, переставлять нельзя
Сравним строки КОТЫ и КИТ. Символы К и Т встречаются в обеих в одном порядке, поэтому КТ — общая подпоследовательность длины 2. В первой строке между ними стоит О, во второй — И. Общая подстрока длины 2 здесь отсутствует: пары КО, ОТ, ТЫ не совпадают с КИ или ИТ.
При поиске подпоследовательности важны позиции, а не только набор букв. Две строки с одинаковыми буквами в обратном порядке могут иметь короткую общую подпоследовательность. Повторяющийся символ нельзя использовать дважды из одной позиции: каждому выбранному символу соответствует отдельное следующее вхождение.
Пример
У КОТЫ и КИТ длина наибольшей общей подпоследовательности равна 2, а общей подстроки — 1.
Строка КТ подходит только под условие с пропусками. Термины определяют разные задачи, несмотря на похожее название.
Что хранится в прямоугольной таблице
Пусть L(i,j) — искомая длина для первых i символов одной строки и первых j символов другой. Если хотя бы один префикс пуст, ответ равен нулю. Когда последние символы равны, их можно добавить к решению для обоих укороченных префиксов: получаем L(i−1,j−1)+1.
Если последние символы различаются, хотя бы один из них не войдёт в общее решение на этих позициях. Выбираем большее из L(i−1,j) и L(i,j−1). Мы не прибавляем единицу просто за наличие буквы где-нибудь в другой строке: такой шаг мог бы нарушить порядок уже выбранных позиций.
Длина и сама последовательность — разные результаты
Для строк АБ и БА максимальная длина равна 1, но возможны два ответа: А и Б. Поэтому программа не обязана возвращать единственную заранее ожидаемую строку. Корректная проверка удостоверяется, что найденный вариант действительно содержится в обеих исходных строках как подпоследовательность и имеет нужную длину.
Чтобы восстановить символы, идём из последней клетки назад по переходам. Совпадение добавляет символ, а переход к соседней клетке пропускает его. Обратный порядок восстановленных символов затем разворачиваем. Одна строка памяти достаточна для длины при аккуратном обновлении, но сама по себе не хранит весь маршрут восстановления.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли сначала отсортировать буквы?
Нет: сортировка уничтожит исходный порядок и изменит задачу. Сравнение множеств также потеряет число повторений и позиции.
Почему при равных вариантах не выбирают сразу оба?
Они описывают альтернативные способы получить одну длину. Складывать длины нельзя: общие позиции могут повториться, а порядок окажется несовместимым.
Углублённый разбор
Восстановление LCS с линейной памятью по Хиршбергу
Две строки динамической таблицы позволяют узнать длину LCS, но не весь обратный путь. Метод Хиршберга восстанавливает саму подпоследовательность, повторно вычисляя только нужные границы и деля задачу на две части.
Перед началом: Динамика LCS; Разделяй и властвуй.
Середина первой строки задаёт место разреза
Разделим A на A_left и A_right приблизительно пополам. Для каждого j вычислим F[j]=LCS_len(A_left,B[:j]) и G[j]=LCS_len(A_right,B[j:]). Первая строка находится обычной динамикой слева, вторая — такой же динамикой на обращённых строках с правильным пересчётом индексов. Для хранения каждой границы достаточно двух строк таблицы.
Выбираем j, максимизирующий F[j]+G[j]. Любая общая подпоследовательность делится в момент перехода между половинами A; соответствующее разбиение B даёт верхнюю границу этой суммой. Обратно, лучшие подпоследовательности двух частей можно соединить: их позиции в обеих строках идут в правильном порядке. Поэтому максимум равен длине глобального оптимума.
| j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| F[j] | 0 | 1 | 1 | 2 | 2 |
| G[j] | 1 | 1 | 1 | 1 | 0 |
| Сумма | 1 | 2 | 2 | 3 | 2 |
Рекурсивное восстановление заменяет полную таблицу
После выбора j решают две задачи(A_left,B[:j]) и(A_right,B[j:]), затем соединяют ответы. Пустая строка даёт пустой результат. При длине одной из строк 1 достаточно проверить наличие её символа в другой. Если максимум достигается при нескольких j, любой согласованный выбор даёт одну LCS; единственность ответа алгоритм не обещает.
Важно освободить временные строки F,G до рекурсивного спуска или переиспользовать память. Если держать большие таблицы границ на каждом уровне, заявленная линейная память может превратиться в дополнительный логарифмический множитель. Передача диапазонов вместо копирования подстрок также отделяет рабочую память алгоритма от случайных затрат реализации.
Повторное вычисление не умножает время на глубину
На первом уровне вычисляется площадь порядка mn. Две рекурсивные задачи используют половины A и непересекающиеся части B, поэтому сумма их площадей примерно вдвое меньше. По уровням получается геометрическая сумма, сохраняющая O(mn) время. Память остаётся линейной с учётом строк, стека и выходной подпоследовательности.
Для проверки результата нужно подтвердить две вещи: полученная строка является подпоследовательностью обеих входных и её длина равна отдельно найденному оптимуму. Одной длины недостаточно: ошибочная склейка может нарушить порядок символов. Одной допустимости тоже недостаточно, поскольку короткая общая подпоследовательность не обязана быть максимальной.
Разрез, который сохраняет оптимум
Условие. A=baca,B=abac. Разделите A на ba и ca, найдите оптимальное разбиение B и восстановите одну LCS.
- Для j=0,…,4 получаем F=[0,1,1,2,2] и G=[1,1,1,1,0]. G относится к суффиксам, а не префиксам B.
- Суммы равны[1,2,2,3,2]. Единственный лучший разрез j=3 делит B на aba и c.
- Для ba и aba можно взять ba; для ca и c — c. Их соединение даёт bac длины 3.
- В A символы bac стоят в позициях 0,1,2, а в B —1,2,3. Оба порядка соблюдены, и длина равна максимуму F+G.
Ответ. Разрез j=3; одна LCS равна bac, длина 3.
Проверка. Перебор всех подпоследовательностей A не находит общей длины 4: строки длины 4 различны. Явная общая bac длины 3 даёт совпадающие нижнюю и верхнюю границы.
Где легко ошибиться. Вторая строка границ относится к суффиксам B. Сложение двух префиксных таблиц с одинаковым направлением не даёт корректный сертификат разреза.
Проверьте понимание
Вопросы к этой главе
Почему нельзя просто восстановить путь из двух последних строк?
Предыдущие строки уже утрачены, а обратный путь может требовать их значений. Хиршберг заново вычисляет только выбранные границы, избегая хранения всей истории.
Нужна самая левая LCS?
Обычный метод возвращает любую оптимальную подпоследовательность. Дополнительный лексикографический либо позиционный критерий требует согласованных правил выбора разрезов и базовых ответов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- D.S.Hirschberg: A Linear Space Algorithm for Computing Maximal Common Subsequences
Первичная статья CACM18(6),341–343: вебом прочитан PDF текст алгоритмов и границы quadratic time/linear space. Две входные строки, строки разбиения и разобранное восстановление созданы отдельно.
Кратчайшая общая надпоследовательность через LCS
Общая надпоследовательность должна содержать обе строки в правильном порядке, но не обязательно подряд. Её минимальная длина связана с LCS, а конструкция объединяет несовпавшие участки вокруг общих символов.
Перед началом: Подпоследовательность; LCS.
Общие позиции можно использовать только в согласованном порядке
Пусть A длины m и B длины n встроены в некоторую общую надпоследовательность S. Позиции S, используемые обеими строками, образуют общую подпоследовательность A и B. Их число не больше L=LCS_len(A,B). Поэтому для размещения всех символов нужно не меньше m+n−L позиций: каждое совместное использование экономит одну позицию.
Нижняя граница не зависит от конкретного алгоритма построения. Она учитывает порядок, а не только частоты букв. Совпадающие символы нельзя объединять произвольно, если их выбранные позиции в двух строках идут в противоположном порядке. Именно поэтому длина LCS, а не размер пересечения множеств символов, входит в формулу.
Слияние вокруг LCS достигает границы
Возьмём одну LCS с указанием её позиций в обеих строках. До первого общего символа выпишем несовпавшие участки A и B, затем общий символ один раз. Повторяем между соседними общими символами и после последнего. Каждая исходная строка читается как подпоследовательность результата, а каждый символ LCS сэкономил ровно одну позицию.
Полученная длина равна m+n−L и потому оптимальна. Разные способы перемежать независимые участки могут давать разные кратчайшие ответы. Для восстановления достаточно хранить выбранный путь LCS либо использовать отдельную динамику надпоследовательности; знание только численной длины L не указывает, какие именно вхождения символов объединять.
Надстрока и надпоследовательность — разные задачи
Если требуется содержать каждую исходную строку непрерывным фрагментом, это задача о надстроке. Пропуски внутри вхождения тогда запрещены, и формула через LCS уже не действует. Общее начало двух строк ещё не позволяет наложить их целиком с произвольными внутренними вставками.
Для контроля готового ответа сначала проверяют оба встраивания двумя указателями, затем сравнивают длину с m+n−L. Два допустимых встраивания доказывают верхнюю границу, а LCS даёт нижнюю. Совпадение границ завершает доказательство оптимальности без необходимости перебирать все возможные надпоследовательности.
Два несовпавших средних символа
Условие. A=axc,B=abc. Постройте кратчайшую общую надпоследовательность и сравните её длину с требованием непрерывного вхождения обеих строк.
- Общая подпоследовательность ac имеет длину 2. Длина 3 невозможна, поскольку обе исходные строки длины 3 и они различны.
- Формула даёт минимальную длину 3+3−2=4. Перед общим c нужно разместить x и b в любом согласованном порядке.
- Строка abxc содержит axc в позициях 0,2,3 и abc в позициях 0,1,3. Она достигает нижней границы 4.
- Для непрерывных вхождений ни одна исходная строка не содержит другую, и ненулевого суффикс-префиксного перекрытия нет. Простая общая надстрока имеет уже длину 6.
Ответ. Одна кратчайшая надпоследовательность abxc, длина 4; кратчайшая надстрока имеет длину 6.
Проверка. Другой оптимальный вариант axbc также содержит обе строки как подпоследовательности. Проверка всех возможных перекрытий длины 1 и 2 между axc,abc не даёт непрерывной надстроки короче 6.
Где легко ошибиться. Формула m+n−LCS относится к надпоследовательности с разрешёнными пропусками. Для непрерывной надстроки нужно исследовать перекрытия целых фрагментов, а не общую подпоследовательность.
Проверьте понимание
Вопросы к этой главе
Если одна строка уже подпоследовательность другой?
Тогда L равна длине меньшей, и формула возвращает длину большей. Сама большая строка является оптимальной общей надпоследовательностью.
Нужно ли объединять каждую одинаковую букву?
Нет. Объединяются только согласованные пары позиций выбранной LCS. Попытка слить все одинаковые буквы может нарушить порядок одной из строк.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- D.S.Hirschberg: A Linear Space Algorithm for Computing Maximal Common Subsequences
Первичная статья CACM18(6),341–343: вебом прочитан PDF текст алгоритмов и границы quadratic time/linear space. Две входные строки, строки разбиения и разобранное восстановление созданы отдельно.
Строка таблицы LCS в разностях и битовом вычитании
Строка таблицы LCS не убывает и увеличивается между соседними столбцами только на0 или 1. Эти приращения можно упаковать в биты. Обновление через OR, сдвиг и вычитание переносит границы уровней сразу по всей строке и позволяет быстро получить длину общей подпоследовательности.
Перед началом: Динамическая таблица LCS; Побитовое вычитание.
Храним изменения строки, а не сами значения
Зафиксируем строку A длины m и последовательно обрабатываем символы B. После очередного префикса B обычная строка DP задаёт L[j]=LCS(A[0:j),B_prefix). Разность L[j+1]−L[j] равна 0 либо 1. Запишем её в бит j состояния S, младший бит соответствует A[0]. Тогда popcount(S)=L[m], а префиксные суммы битов восстанавливают всю строку DP.
Для каждой буквы c предвычислим маску M[c] позиций её появления в A. Начальное S=0 соответствует пустому префиксу B. В отличие от Shift-And биты здесь не означают точное совпадение префикса образца: это места повышения оптимальной длины подпоследовательности. Одинаковая внешняя форма битовой маски не делает два инварианта взаимозаменяемыми.
Займы при вычитании находят следующую границу уровня
Для очередной буквы c вычислим x=S|M[c], y=(S<<1)|1, затем S_new=x & ~(x−y), сохраняя только m младших битов. Вычитание можно понимать по модулю 2ᵐ; AND с x удаляет все старшие разряды. Единицы y запускают поиск следующего подходящего места в сегментах между прежними границами уровней, а распространение займа проходит через нули до первой доступной единицы x.
Эта первая единица либо сохраняет прежнюю границу, либо переносит её к более раннему подходящему совпадению новой буквы. Именно такие минимальные позиции окончания представляют уровни строки LCS. Поэтому операция эквивалентна обычному обновлению DP, но обрабатывает сегменты параллельно. В реализации на нескольких словах нужны переносы сдвига и займа между соседними словами; независимое вычитание каждого блока дало бы неверный результат.
Длина получается легко, восстановление требует дополнительной работы
При w-битных словах стоимость обработки B составляет O(|B|ceil(m/w)) после масок. Это не постоянная операция над строкой произвольной длины. Полученный popcount даёт только длину LCS; для восстановления конкретных символов нужны сохранённые строки, обратный ход либо отдельная техника разбиения. Пустая A даёт нулевую длину без отрицательного сдвига, а неизвестная буква имеет M[c]=0. Эти границы удобно проверить полной обычной DP независимо от битовой формулы.
Пять обновлений с тремя итоговыми единицами
Условие. Найдите длину LCS для A=cabca и B=acbac битовой формулой. Все маски записывайте пятью битами, младший справа.
- Маски равны M[a]=10010₂,M[b]=00100₂,M[c]=01001₂. Начальное S=00000₂.
- После a получаем 00010₂, после c —01001₂. Например, на втором шаге x=01011₂,y=00101₂, x−y=00110₂, и AND с дополнением даёт 01001₂.
- После следующих b,a,c состояния равны 00101₂,10011₂,01011₂. Числа установленных битов по пяти строкам равны 1,2,2,3,3.
- Финальное S=01011₂ имеет 3 единицы, поэтому длина LCS равна 3. Подпоследовательность abc встречается в A на индексах 1,2,3 и в B на0,2,4, подтверждая нижнюю границу.
Ответ. Длина LCS равна 3; конечная маска 01011₂ кодирует строку DP[0,1,2,2,3,3].
Проверка. Независимая полная таблица DP подтверждает каждую промежуточную строку и конечную длину. Перебор всех подпоследовательностей A не находит общей длины 4, а явная abc имеет длину 3.
Где легко ошибиться. Не трактуйте установленные биты как сами символы одной LCS и не вычитайте отдельные машинные слова без передачи займа. Биты кодируют изменения оптимальных префиксных длин.
Проверьте понимание
Вопросы к этой главе
Почему на шаге b число единиц не увеличилось?
Новый символ может улучшить места достижения уже имеющихся длин, не увеличив максимальную длину. Маска меняется с01001 на00101, но обе имеют 2 единицы: это перенос границы, а не потеря корректности.
Можно ли просто прочитать буквы A в установленных позициях финальной маски?
Нет. Финальная строка хранит минимальные границы достижения разных длин для одного префикса B, а не согласованную цепочку предков одного решения. Для восстановления нужны дополнительные связи или отдельный алгоритм.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Allison, Dix: A Bit-String Longest-Common-Subsequence Algorithm, §2
Прочитан авторский полный текст 1986: разности строк DP, alphabet strings и вычитание с распространением займа. Использована эквивалентная форма x & ~(x−y); свой worked cabca/acbac и все короткие бинарные проверки независимы от генетического примера статьи.
Число различных LCS не равно числу оптимальных выравниваний
Одна и та же наибольшая общая подпоследовательность может иметь несколько выравниваний в исходных строках. Поэтому подсчёт оптимальных путей таблицы динамики способен завысить число различных ответов. Каноническое продолжение по первой букве отделяет разные строки и устраняет повторные способы выбрать одинаковые символы.
Перед началом: Суффиксная таблица длины LCS; Различие строки и её вхождения.
Считать нужно результаты, а не способы удаления
Пусть L(i,j) — длина LCS суффиксов A[i:] и B[j:]. Обычная таблица определяет оптимальную длину и позволяет восстановить один ответ. Но ветви «пропустить символ A» и «пропустить символ B» могут прийти к одной и той же результирующей строке. Простое сложение числа таких ветвей считает пути, а не различные подпоследовательности.
Даже фиксированная строка может иметь несколько наборов позиций. Если два одинаковых символа подряд разрешают выбрать любой из них, слово результата не меняется. Поэтому для подсчёта различных LCS нужно либо хранить множества строк с удалением повторов, либо строить представление, в котором каждый ответ имеет единственный путь.
Ранние вхождения создают канонический переход
Для каждой буквы c найдём её самые ранние позиции p≥i в A и q≥j в B. Если обе существуют и 1+L(p+1,q+1)=L(i,j), разрешим переход с меткой c к состоянию (p+1,q+1). Перебираем разные буквы, а не разные пары одинаковых букв.
Почему ранних вхождений достаточно: любое оптимальное продолжение, начинающееся с c, использует не более ранние позиции. Замена первой выбранной пары на самые ранние вхождения оставляет не меньше места для хвоста. Хвост длины L−1 сохраняется, а более длинный противоречил бы оптимальности исходного L. Поэтому ни один различный оптимальный ответ не теряется.
Подсчёт на ациклическом графе имеет простую базу
Каждый переход увеличивает обе позиции, поэтому граф состояний ацикличен. В состоянии с L=0 существует ровно один хвост — пустая строка. Для остальных состояний количество ответов равно сумме количеств хвостов по допустимым буквам. Разные первые буквы дают непересекающиеся множества ответов, а внутри одной буквы переход каноничен.
Мемоизация позволяет повторно использовать одинаковые состояния суффиксов. Число различных ответов может быть большим, поэтому время их полного вывода нельзя ограничить только размером таблицы длин. Подсчёт без вывода и перечисление всех строк имеют разную стоимость. Для малого примера полный перебор подмножеств позиций является удобной независимой проверкой канонического графа.
Повторные буквы не создают новые слова ответа
Условие. Для A=aaba и B=abaa найдите длину и все различные LCS. Сравните число слов с числом способов расположить слово aba в обеих строках.
- Длина LCS равна трём. Общие строки aaa и aba достигают этой длины, а длина четыре невозможна: исходные строки длины четыре различаются.
- Первой буквой любого оптимального ответа является a. Её ранние позиции равны нулю в обеих строках; оставшиеся суффиксы имеют оптимальный хвост длины два.
- После первой a допустимы следующие первые буквы хвоста a и b. Они дают соответственно хвосты aa и ba, поэтому полный список слов равен {aaa,aba}.
- Слово aba имеет два вхождения в A: первую a можно выбрать в позиции ноль или один. В B последнюю a можно выбрать в позиции два или три. Получаются четыре пары выравниваний одного и того же слова.
- Полный перебор подпоследовательностей обеих строк с объединением по значению оставляет ровно два максимальных слова. Канонический граф получает то же число без четырёхкратного повторения aba.
Ответ. Длина равна 3; различные LCS — aaa и aba, всего две. Одно слово aba само по себе допускает четыре пары позиционных выравниваний.
Проверка. Перечисление всех подмножеств четырёх позиций независимо проверяет множество максимальных общих строк и отдельно число вхождений aba.
Где легко ошибиться. Не суммируйте оптимальные пути обычной таблицы, если запрос требует количество различных строк. Одинаковая LCS может появляться на нескольких путях и в нескольких выравниваниях.
Проверьте понимание
Вопросы к этой главе
Почему в базе L=0 количество равно одному, а не нулю?
Существует один пустой хвост. Он нужен как нейтральное продолжение последней выбранной буквы; нулевая база ошибочно занулила бы все количества.
Можно ли выбирать любую пару вхождений первой буквы?
Для существования ответа это возможно, но для однозначного подсчёта создаёт дубли. Ранние вхождения доминируют по доступному хвосту и задают один канонический переход на букву.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Y. Sakai: LCS enumeration of two strings
Прочитаны введение и определения различия подпоследовательности и её вхождения, а также описание DAG без повторных LCS. Конкретная канонизация через ранние вхождения доказана и проверена здесь отдельно; сложные оценки пространства и задержки из статьи не присваиваются этому учебному алгоритму.
LCS через пары совпадений и возрастающую подпоследовательность
Если две длинные строки редко имеют одинаковые символы, прямоугольная таблица LCS обрабатывает много пустых клеток. Алгоритм Ханта—Шиманского рассматривает только пары равных символов. Каждая общая подпоследовательность становится цепочкой пар, в которой обе координаты строго растут. Задача сводится к возрастающей подпоследовательности специального списка позиций; порядок внутри одной строки не позволяет использовать один символ дважды.
Перед началом: Общая подпоследовательность и её отличие от подстроки; Двоичный поиск первого элемента не меньше заданного.
Одна цепочка использует каждую позицию не более одного раза
Конечные строки, точное равенство символов, длина общей подпоследовательности; индексы начинаются с нуля.
Для каждого символа A[i] выпишем все позиции j, где B[j]=A[i]. Обрабатываем i слева направо, а соответствующие j — строго справа налево. В полученном числовом списке ищем строго возрастающую подпоследовательность. Она не может взять две позиции из одного блока: внутри блока числа убывают. Порядок блоков одновременно гарантирует рост первой координаты.
Обратно, любая общая подпоследовательность задаёт возрастающие пары и выбирает подходящие элементы списка. Поэтому оптимальные длины совпадают. Убывание внутри блока существенно: для A=a и B=aa возрастающий блок 0,1 ошибочно дал бы ответ 2, хотя у первой строки только один символ. Правильный блок 1,0 имеет строго возрастающую подпоследовательность длины 1.
Минимальные концы сохраняют возможность продолжения
Массив tails[k] хранит наименьшую возможную последнюю позицию цепочки длины k+1 среди уже обработанных совпадений. Для очередного j находим первый элемент tails, который не меньше j, и заменяем его на j. Если такого нет, добавляем новый конец. Меньший конец оставляет не меньше возможностей продолжить цепочку будущими позициями.
Поиск именно первого значения не меньше j обеспечивает строгий рост: равная позиция не увеличивает длину. Сам массив tails не обязан представлять одну конкретную общую подпоследовательность, поскольку его элементы могли происходить из разных цепочек. Для восстановления текста сохраняют предшественников отдельных совпадений; для одной длины достаточно массива концов.
Разреженность определяется числом совпадающих пар
Если r — число пар равных символов, обработка занимает O(r log(min(m,n)+1)) после построения списков позиций. При постоянном алфавите или подходящем словаре подготовка занимает O(m+n). Это полезно, например, при сравнении последовательностей редких идентификаторов: длины велики, но совпадающих пар мало.
Оценка не обещает ускорение для любых строк. У двух строк из одной повторяющейся буквы r=mn, хотя ответ очевиден. В такой ситуации плотная динамика или специальная битовая обработка могут быть практичнее. Выбирать алгоритм следует по распределению символов, а не по одному размеру входа.
Семь символов, восемь символов и одиннадцать совпадений
Условие. Найдите длину LCS строк A=axbyazc и B=bayxacaz методом списков совпадений. Индексы обеих строк начинаются с нуля.
- В B позиции a равны 1,4,6; x находится в 3, b в 0, y в 2, z в 7, c в 5. Блоки для A получаются 6,4,1; 3; 0; 2; 6,4,1; 7; 5.
- После первого блока tails=[1]. Последующие символы x,b,y дают соответственно [1,3], [0,3], [0,2]. Меньший конец меняет возможность продолжения, но не обязательно всю восстановленную цепочку.
- После второго a массив равен [0,1,4]. Символ z расширяет его до [0,1,4,7], а c заменяет последний конец: [0,1,4,5]. Полученная длина равна 4.
- Отдельный свидетель — axaz: позиции A равны 0,1,4,5, а позиции B равны 1,3,4,7. Все четыре пары возрастают, поэтому найденная нижняя граница достигается.
Ответ. Длина LCS равна 4; один допустимый ответ — axaz.
Проверка. Независимая прямоугольная динамика по исходным строкам даёт 4. Перебор всех подпоследовательностей семисимвольной A также не находит общей последовательности длины 5; конечный tails не используется как готовый текст ответа.
Где легко ошибиться. Не сортируйте совпадения одного символа по возрастанию позиций второй строки. Тогда одна позиция первой строки сможет породить несколько элементов ложной цепочки.
Проверьте понимание
Вопросы к этой главе
Почему одинаковые значения j не должны увеличивать ответ?
Они соответствуют одной позиции B. Общая подпоследовательность использует позицию только один раз, поэтому нужен строгий рост и замена первого конца, не меньшего j.
Можно заранее определить число обрабатываемых пар?
Да. Если fA(c) и fB(c) — частоты символа, то r равно сумме fA(c)fB(c). Эта величина помогает оценить, даст ли разреженная обработка преимущество перед плотной таблицей.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Hirschberg — Serial Computations of Levenshtein Distances, §4.4.2
Убывающие списки совпадений и пороги минимальных концов в разреженном алгоритме LCS. Строки и обе независимые проверки примера составлены отдельно.
Индекс следующего вхождения отвечает на запросы подпоследовательностей
Когда текст фиксирован, а запросов много, для каждого запроса не требуется заново вычислять LCS. Достаточно знать следующее вхождение каждой буквы после уже выбранной позиции. Таблица таких переходов превращает запрос в путь по состояниям текста. Жадный выбор самого раннего символа корректен: он оставляет для продолжения не меньше места, чем любой другой допустимый выбор.
Перед началом: Подпоследовательность с сохранением порядка; Таблица переходов детерминированного автомата.
Состояние хранит границу уже использованного префикса
Много запросов существования подпоследовательности в одном неизменном тексте; конечный явно заданный алфавит.
Нумеруем символы T с нуля. Состояние p означает, что следующие позиции можно выбирать начиная с p; начальное состояние равно 0. Определим next[p,c] как наименьший индекс j≥p с T[j]=c либо специальное значение «нет». После выбора j переходим в p=j+1, чтобы не использовать ту же позицию повторно.
Состояния 0,…,n принимают завершившийся запрос: пустое оставшееся слово допустимо после любого уже найденного префикса. Из состояния n непустого перехода нет. Если буква запроса отсутствует в алфавите текста, ответ сразу отрицательный. Отсутствие перехода означает корректный отказ запроса, а не ошибку построения индекса.
Ранний выбор доминирует любой другой частичный ответ
Докажем по длине прочитанного запроса, что жадный путь заканчивается не правее любого другого вложения того же префикса. Для пустого префикса это очевидно. Если некоторое альтернативное вложение выбрало следующую букву в j, его предыдущая граница не меньше жадной; значит j доступно и жадному выбору. Минимальное доступное вхождение находится не позже j.
Поэтому отсутствие следующей буквы у жадного пути исключает её и у всех альтернатив. Если путь завершился, выбранные индексы сами служат свидетельством существования подпоследовательности. Обратный выбор самой поздней подходящей буквы таким свойством не обладает и может без необходимости исчерпать текст.
Плотная таблица и списки позиций дают разные расходы
Плотную next-таблицу строят справа налево: строка n содержит только отсутствие, строка p копирует p+1 и меняет запись буквы T[p] на p. При алфавите размера σ это O(nσ) времени и памяти; каждый запрос длины m затем занимает O(m) переходов. Если σ велико, такая таблица может оказаться неоправданно большой.
Альтернатива — хранить отсортированный список позиций каждой буквы и искать первое значение не меньше текущей границы двоичным поиском. Память становится линейной по длине текста, а запрос требует до O(m log n). Ни одно представление не считает число разных вложений: жадный путь сохраняет один ранний свидетель существования.
Один индекс обслуживает успешные и неуспешные запросы
Условие. Для текста T=abacbaba обработайте запросы abbaa, caba, cabb и aaaaa. Используйте позиции с нуля, выбирая каждое следующее вхождение как можно раньше.
- Списки позиций равны a:[0,2,5,7], b:[1,4,6], c:[3]. Для запроса abbaa последовательные переходы выбирают 0,1,4,5,7. Границы после них равны 1,2,5,6,8.
- Запрос caba выбирает 3,5,6,7 и также принимается. Если для первого a в abbaa преждевременно выбрать позицию 2, дальнейшие b займут 4,6, а двух последующих a уже не хватит.
- Запрос cabb выбирает c в 3, a в 5, b в 6. Следующего b после границы 7 нет, поэтому запрос отклоняется. Другой выбор не поможет по свойству самого раннего пути.
- Запрос aaaaa использует a в 0,2,5,7 и останавливается на пятой букве. В тексте всего четыре a. Пустой запрос, в отличие от него, принимается без единого перехода.
Ответ. abbaa и caba существуют как подпоследовательности; cabb и aaaaa не существуют.
Проверка. Независимый перебор возрастающих наборов индексов подтверждает ровно эти ответы. Он также показывает, что успешный путь задаёт существование, а не обязательно единственность вложения; например, односимвольный запрос a имеет четыре вложения.
Где легко ошибиться. После выбора индекса j обновляйте границу до j+1. Повторный поиск с границы j позволяет использовать один символ текста несколько раз и ошибочно принять слишком длинный запрос.
Проверьте понимание
Вопросы к этой главе
Почему все состояния могут быть принимающими?
Каждый достигнутый путь уже прочитал некоторую подпоследовательность текста. Если запрос на этом закончился, дополнительных требований к оставшемуся суффиксу нет.
Можно этим же путём посчитать все вложения запроса?
Нет. Ранний путь намеренно отбрасывает альтернативы, сохраняя лишь возможность продолжения. Для количества вложений нужна другая динамика, которая суммирует допустимые выборы.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Bille, Gørtz, Skjoldjensen — Subsequence Automata, §2
Стандартный автомат подпоследовательностей: принимающие состояния и переход к ближайшему следующему символу. Здесь используется обычная таблица без переходов по умолчанию; примеры и доказательство жадного выбора подготовлены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему в задаче о рюкзаке предмет нельзя использовать дважды незаметно
Собираем набор приборов в рюкзак и показываем, почему направление обновления одномерной таблицы отличает выбор 0/1 от неограниченных повторов.
Открыть темуПочему изменение строки создаёт другое значение
Отличаем изменение имени от изменения строки в Python, сохраняем результат replace и сравниваем строки со списками символов без подмены кодовой точки видимой буквой.
Открыть тему