* Объединяем оба редакционных предписания.
В псевдокоде:===Псевдокод===
<code>
'''int''' '''levensteinInstruction'''('''String''' s1, '''String''' s2): '''if''' ( s1.length <tex> \leqslant </tex> = 1 || s2.length <tex> \leqslant </tex> = 1 )
Решаем тривиально, возвращаем редакционное предписание
//Иначе:'''else''' String s1l, s1r, s2l, s2r '''if''' ( s2.length < s1.length ) s1l = s1.substring(0, s1.length / 2) // <tex>S_1^S1-</tex> s1r = s1.substring(s1.length / 2, s1.length) // <tex>S_1^S1+</tex> // d, e - массивы d = '''calcD'''(s1l, s2) // Вычисляем последнюю строку матрицы <tex>D</tex> для <tex>S_1^S1-</tex> и <tex>S_2</tex>S2 e = '''calcE'''(s1r, s2) // Вычисляем последнюю строку матрицы <tex>E</tex> для <tex>S_1^S1+</tex> и <tex>S_2</tex>S2 k = 0 '''for''' i = 1..'''to''' s2.length '''if''' (d[i] + e[s2.length - i] < d[k] + e[s2.length - k]) k = i s2l = s2.substring(0, k) s2r = s2.substring(k, s2.length) '''else''' //s1 - меньшая строка s2l = s2.substring(0, s2.length / 2) // <tex>S_2^S2-</tex> s2r = s2.substring(s2.length / 2, s2.length) // <tex>S_2^S2+</tex> d = '''calcD'''(s2l, s1) // Вычисляем последнюю строку матрицы <tex>D</tex> для <tex>S_2^S2-</tex> и <tex>S_1</tex>S1 e = '''calcE'''(s2r, s1) // Вычисляем последнюю строку матрицы <tex>E</tex> для <tex>S_2^S2+</tex> и <tex>S_1</tex>S1 k = 0 '''for''' i = 1..'''to''' s1.length '''if''' (d[i] + e[s1.length - i] < d[k] + e[s1.length - k]) k = i s1l = s1.substring(0, k) s1r = s1.substring(k, s1.length)
'''return''' '''levensteinInstruction'''(s1l, s2l) + '''levensteinInstruction'''(s1r, s2r)
