Изменения

Для того, чтобы обеспечить время <mathtex>\Theta(M \cdot N)</mathtex> при памяти <mathtex>\Theta(\min(M,N))</mathtex>, определим матрицу <tex> E </tex> минимальных расстояний между ''суффиксами'' строк, то есть <tex> E(i, j) — </tex> {{---}} расстояние между последними <tex> i </tex> символами <mathtex>S_1</mathtex> и последними <tex> j </tex> символами <mathtex>S_2</mathtex>. Очевидно, матрицу <tex> E </tex> можно вычислить аналогично матрице <tex> D</tex>, и так же быстро.

Теперь опишем алгоритм, считая, что <mathtex>S_2</mathtex> — кратчайшая из двух строк.

* Если длина одной из строк (или обеих) не больше <tex> 1</tex>, задача тривиальна. Если нет, выполним следующие шаги.* Разделим строку <mathtex>S_1</mathtex> на две подстроки длиной <mathtex>M/2</mathtex>. (Если <tex>M </tex> нечётно, то длины подстрок будут <mathtex>(M-1)/2</mathtex> и <mathtex>(M+1)/2</mathtex>.) Обозначим подстроки <mathtex>S_1^-</mathtex> и <mathtex>S_1^+</mathtex>.* Для вычислим последнюю строку матрицы <tex> D </tex> для строк <mathtex>S_1^-</mathtex> и <mathtex>S_2</mathtex>, последнюю строку матрицы <tex> E </tex> для строк <mathtex>S_1^+</mathtex> и <mathtex>S_2</mathtex>.* Найдём <tex> i </tex> такое, что <mathtex>D(|S_1^-|, i) + E(|S_1^+|, N-i)</mathtex> минимально. Здесь <tex> D </tex> и Е — <tex> E </tex> {{---}} матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение <mathtex>S_2</mathtex> на две подстроки, минимизирующее сумму расстояния левой половины <mathtex>S_1</mathtex> до левой части <mathtex>S_2</mathtex> и расстояния правой половины <mathtex>S_1</mathtex> до правой части <mathtex>S_2</mathtex>. Следовательно, левая подстрока <mathtex>S_2</mathtex> соответствует левой половине <mathtex>S_1</mathtex>, а правая — правая {{---}} правой.* Рекурсивно ищем редакционное предписание, превращающее <mathtex>S_1^-</mathtex> в левую часть <mathtex>S_2</mathtex> (то есть в подстроку <mathtex>S_2[1...i]</mathtex>)* Рекурсивно ищем редакционное предписание, превращающее <mathtex>S_1^+</mathtex> в правую часть <mathtex>S_2</mathtex> (то есть в подстроку <mathtex>S_2[i+1...N]</mathtex>).

'''String''' '''levensteinInstruction'''('''String''' s1, '''String''' s2){ '''if''' ( s1.length <= tex> \le </tex> 1 || s2.length <= tex> \le </tex> 1 )

'''String''' s1l, s1r, s2l, s2r

s1l = s1.substring(0, s1.length / 2) //<mathtex>S_1^-</mathtex> s1r = s1.substring(s1.length / 2, s1.length) //<mathtex>S_1^+</mathtex> '''int''' [] // d, e - массивы d = '''calcD'''(s1l, s2) //Вычисляем последнюю строку матрицы <tex>D </tex> для <mathtex>S_1^-</mathtex> и <mathtex>S_2</mathtex> '''int''' [] e = '''calcE'''(s1r, s2) //Вычисляем последнюю строку матрицы <tex>E </tex> для <mathtex>S_1^+</mathtex> и <mathtex>S_2</mathtex> '''int''' k = 0 '''for''' ('''int''' i = 1; i <= ..s2.length; i++)

s2l = s2.substring(0, s2.length / 2) //<mathtex>S_2^-</mathtex> s2r = s2.substring(s2.length / 2, s2.length) //<mathtex>S_2^+</mathtex> '''int''' [] d = '''calcD'''(s2l, s1) //Вычисляем последнюю строку матрицы <tex>D </tex> для <mathtex>S_2^-</mathtex> и <mathtex>S_1</mathtex> '''int''' [] e = '''calcE'''(s2r, s1) //Вычисляем последнюю строку матрицы <tex>E </tex> для <mathtex>S_2^+</mathtex> и <mathtex>S_1</mathtex> '''int''' k = 0 '''for''' ('''int''' i = 1; i <= ..s1.length; i++)

: <mathtex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N'),\ 0\le N'\le N</mathtex>,

: <mathtex>T(M,N) \le 2MN</mathtex>

: <mathtex>T(1,N) = N \le 2N</mathtex>Пусть для всех <mathtex>M' < M</mathtex> выполнено <mathtex>T(M',N') \le 2M'N'</mathtex>. Тогда учитывая <mathtex>T(M/2,N') \le 2(M/2)N'</mathtex>, <mathtex>T(M/2,N-N') \le 2(M/2)(N-N')</mathtex>, получим:: <mathtex>T(M,N)=MN+T(M/2,N')+T(M/2,N-N') \le</mathtex> <mathtex> MN+2(M/2)N'+2(M/2)(N-N')=2MN</mathtex>

: <mathtex>T(M,N) = \Theta(M \cdot N)</mathtex>

Для вычисления последних строк матриц <tex> D, ~E </tex>можно использовать два глобальных двумерных массива размера <mathtex>2 \times (min(M, N)+1)</mathtex>.

Т.к. мы вычисляем функцию рекурсивно, требуемый размер стека тоже следует учесть. На стек вызовов потребуется <mathtex>\Theta(log(max(M,N))</mathtex> памяти, потому общая оценка использования памяти будет <mathtex> \Theta(min(M,N)) </mathtex>