Page 232 - Bkhargava_-_Grokaem_algoritmy

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

А это моя формула для заполнения ячеек:

1. ЕСЛИ БУК&ЬI
НЕ СО&ПА.П.АIОТ,
JНАЧЕ.НИЕ. н 5 н
РА&НО О
F о о о о

о о о

5 о о о
н~о о 3

2.. ЕСЛИ ОНИ СО&ПА.Q.АЮТ,
ТО .ЗНАЧЕНИЕ РА&НО
JHA Ч Е.НИIО JIЧ Е.~КИ
НА&ЕРХУ СЛЕ&А +1

На псевдокоде эта формула реализуется так:

if word_a[ i] == word_b[ j]: -<· Буквы совпадают
cell[i][j] " cell[i-l][j-1] + 1 -с: · " " · Буквы не совпадают
else:
cell[i][j] " 0

Аналогичная таблица для строк hish и vista:

v S ТА

~ о о о о о
1 о 1 о о о
s о о 2 о о
н о о о о о

t
ОКОНЧА- НЕОКОНЧА-
ТЕЛЬНЫК ТЕ.ЛЬНЫК
ОТ& Е.Т ОП\ ЕТ

www.trk.kg