Page 233 - Bkhargava_-_Grokaem_algoritmy

232 Глава 9. Динамическое программирование

Важный момент: в этой задаче окончательное решение далеко не всегда на­
ходится в последней ячейке! В задаче о рюкзаке последняя ячейка всегда
содержит окончательное решение. Но в задаче поиска самой длинной общей
подстроки решение определяется самым большим числом в таблице - и это
может быть не последняя, а какая-то другая ячейка.

Вернемся к исходному вопросу: какая строка ближе к hish? У строк hish
и fish есть общая подстрока длиной в три буквы. У hish и vista есть общая
подстрока из двух букв. Скорее всего, Алекс хотел ввести строку fish.

Самая длинная общая подпоследовательность

Предположим, Алекс ввел строку fosh. Какое слово он имел в виду: fish
илиfоrt?

Сравним строки по формуле самой длинной общей подстроки.

F О 5 н F о .s н

F t о о о F ' () о о

о о 2 о о о о о о
или
R о о о о 5 о о 1 о

т о о о о н о о о 2

Длина подстрок одинакова: две буквы! Hofosh при этом ближе кfish:

F о 5 н
,j, о1, .... =- ;?
FI S н

f о ~ 1-1
J.. ... :: 2
F О R Т

www.trk.kg