Фундаментальные алгоритмы и структуры данных в Delphi

Для начала предположим, что нам удалось найти наиболее длинную общую подпоследовательность двух слов (далее для ее обозначения мы будем использовать аббревиатуру "LCS"). В этом случае можно было бы соединить линиями буквы в LCS первого слова с буквами LCS второго слова. Эти линии не будут пересекаться. (Это обусловлено тем, что подпоследовательности определены так, что перестановки букв не допускаются. Поэтому буквы в LCS в обоих словах будут располагаться в одинаковом порядке.) LCS для слов "banana" и "abracadabra" (т.е. b, а, а, а) и линии, соединяющие совпадающие в них буквы, показаны на рис. 12.1. Обратите внимание, что для этой пары слов существует несколько возможных LCS. На рисунке, показана лишь первая из них (занимающая самую левую позицию).

Рисунок 12.1. LCS для слов "banana" и "abracadabra"

Итак, тем или иным способом мы определили LCS двух слов. Предположим, что длина этой подпоследовательности равна х. Взгляните на последние буквы обоих слов. Если ни одна из них не является частью соединительной линии, и при этом они являются одной и той же буквой, то эта буква должна быть последней буквой LCS и между ними должна была бы существовать соединительная линия. (Если эта буква не является последней буквой подпоследовательности, ее можно было бы добавить, удлинив LCS на одну букву, что противоречило бы сделанному предположению о том, что первая подпоследовательность является самой длинной.) Удалим эту последнюю букву из обоих слов и из подпоследовательности.

Полученная сокращенная подпоследовательность длиной x - 1 представляет собой LCS двух сокращенных слов. (Если бы это было не так, для двух сокращенных слов должна была бы существовать общая подпоследовательность длиной X или больше. Добавление заключительных букв привело бы к увеличению длины новой общей подпоследовательности на единицу, а, значит, для двух полных слов должна была бы существовать общая подпоследовательность, содержащая x+1 или более букв. Это противоречит предположению о том, что мы определили LCS.)

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

Все это замечательно, но о чем же оно свидетельствует? LCS содержит в себе LCS усеченных частей обоих слов. Для отыскания LCS строк X и Y мы разбиваем задачу на более мелкие задачи. Если бы последние символы слов X и Y совпадали, нам пришлось бы найти LCS для строк X и Y без их последних букв, а затем добавить эту общую букву. Если нет, нужно было бы найти LCS для строки X без последней буквы и строки Y, а также LCS строки X и строки Y без ее последней буквы, а затем выбрать более длинную из них. Мы получаем простой рекурсивный алгоритм.

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

Мы пытаемся вычислить LCS двух строк X и Y. Вначале мы определяем, что строка X содержит n символов, а строка Y - m. Обозначим строку, образованную первыми i символами строки X, как Х(_i_). i может принимать также нулевое значение, что означает пустую стоку (это соглашение упростит понимание алгоритма). В таком случае Х(_n_) соответствует всей строке. С применением этой формы записи алгоритм сводится к следующему; если последние два символа строк Х(_n_) и Y(_m_) совпадают, самая длинная общая последовательность равна LCS Х(_n-1_) и Y(_m-1_) с добавлением этого последнего символа. Если они не совпадают, LCS равна более длинной из LCS строк Х(_n-2_) и Y(_m_) и LCS строк Х(_n_) и Y(_m-1_). Для вычисления этих "меньших" LCS мы рекурсивно вызываем одну и ту же подпрограмму.

Тем не менее, обратите внимание, что для вычисления LCS строк Х(_n-1_) и Y(_m_) может потребоваться вычислить LCS строк Х(_n-2_) и Y(_m-1_), LCS строк Х(_n-1_) и Y(_m-1_) и LCS строк Х(_n-2_) и Y(_m_). Вторую из этих подпоследовательностей можно уже вычислить. При недостаточной внимательности можно было бы вычислять одни и те же LCS снова и снова. В идеале во избежание этих повторных вычислений нужно было бы кешировать ранее вычисленные результаты. Поскольку мы располагаем двумя индексами для строк X и Y, имеет смысл воспользоваться матрицей.