Page 234 - Bkhargava_-_Grokaem_algoritmy

Самая длинная общая подстрока 233

Мы сравниваем самую длинную общую подстроку, а на самом деле нужно
сравнивать самую длинную общую подпоследовательность: количество
букв в последовательности, общих для двух слов. Как вычислить самую
длинную общую подпоследовательность?

Ниже приведена частично заполненная таблица для fish и f osh.

F О 5 Н
1 1
1
с; 1 2 2
н

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

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

Окончательная версия таблицы:

F О s F ~ н

F F
2
о \
2 s

2 2 н

C.AMAJI JlЛMHHAJI OIЩAJI C.AMAJI JlЛMHHAJI OБ\4AJI
П OJl.П ОС.Л ЕЛ.О 6 А­ П OJl.П ОС.Л ЕЛ.О 6 А­
ТЕЛ ЬН ОС. ТЬ • 2. ТЕ.Л ЬН ОС. ТЬ • ~

www.trk.kg