Поиск самой длинной общей подпоследовательности (LCS) двух строк — классическая задача информатики.

Задача состоит в том, чтобы найти самую длинную подпоследовательность, присутствующую в обеих строках.

Подпоследовательность отличается от подстроки тем, что она не обязательно должна быть непрерывной. «AB» и «BC» являются подстроками «ABC», а также обе являются подпоследовательностью «ABC», поскольку все подстроки являются подпоследовательностью. «AC» также является подпоследовательностью «ABC», потому что элементы «AC» появляются в том же порядке, что и в «ABC» — вам просто нужно пропустить «B». Однако «AC» не является подстрокой «ABC», поскольку подстрока должна быть непрерывной или не пропускать какие-либо элементы.

Наивный подход

Наивный подход к проблеме LCS состоит в том, чтобы генерировать все подпоследовательности одной из строк и перебирать их от самой длинной к самой короткой, пока не будет найдена одна, которая также может быть найдена в другой строке.

Этот подход подходит для небольших строк. Например, вот все подпоследовательности «ABC»: «A», «B», «C», «AB», «AC», «BC», «ABC» и «» (пустая строка).

Но для более длинных строк время вычислений может быть слишком большим. Это связано с тем, что время обработки этого метода увеличивается на 2ⁿ, где n — длина строки.

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

Таким образом, генерация всех подпоследовательностей функционально аналогична подсчету в двоичном формате до числа той же длины, что и исходная строка. Поскольку каждая позиция в двоичной строке соответствует степени числа 2, каждый дополнительный элемент в исходной строке удваивает время вычислений.

Таким образом, наивный подход бесполезен для большинства приложений.

Использование динамического программирования и мемоизации

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

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

Решение

Сначала возьмите две входные строки. Назначьте их как X и Y.

Затем в начало X и Y необходимо добавить «пустой» элемент. В примере используется «0» (или строка (0)) — хотя, если строка (строки) может содержать этот элемент, тогда следует использовать другой элемент вне алфавита строки. Этот шаг упрощает доступ к индексу.

Теперь необходимо создать таблицу. Количество строк должно быть равно длине X, а количество столбцов должно быть равно длине Y.

Когда настройка завершена, может вступить в действие алгоритм.

Начиная с X0, Y0, итерировать каждый квадрат в каждой строке до Xi, Yj, выполняя следующую операцию:

  • Если текущий квадрат находится в X-индексе 0 ИЛИ Y-индексе 0, то вставьте пустой объект в таблицу в текущем квадрате.
  • В противном случае, если элементы Xi и Yj равны, то текущим квадратом является элемент в квадрате слева вверху плюс элемент Xi.
  • В противном случае, если элементы Xi и Yj не равны, то текущий квадрат является самой длинной последовательностью между элементом в квадрате непосредственно над ним и квадратом непосредственно слева от текущего.

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

Одно значение приведет к тому, что самая длинная общая подпоследовательность будет возвращать одну самую длинную общую подпоследовательность. Хотя гарантированно будет самая длинная общая подпоследовательность, она не гарантируется единственной.

Полный пример кода

Ниже приведен полный исходный код программы, которая будет возвращать самую длинную общую подпоследовательность из двух строк: