Алгоритм поиска расстояния редактирования до всех подстрок

Учитывая 2 строки s и t . Мне нужно найти для каждой подстроки в s расстояние редактирования (расстояние Левенштейна) до t . На самом деле мне нужно знать для каждой позиции i в s , каково минимальное расстояние редактирования для всех подстрок, начинающихся с позиции i .

Например:

t = "ab"    
s = "sdabcb"

И мне нужно получить что-то вроде:

{2,1,0,2,2}

Пояснение:

1st position:
distance("ab", "sd") = 4 ( 2*subst )
distance("ab", "sda") = 3( 2*delete + insert )
distance("ab", "sdab") = 2 ( 2 * delete)
distance("ab", "sdabc") = 3 ( 3 * delete)
distance("ab", "sdabcb") = 4 ( 4 * delete)
So, minimum is 2

2nd position:
distance("ab", "da") = 2 (delete + insert)
distance("ab", "dab") = 1 (delete)
distance("ab", "dabc") = 2 (2*delete)
....
So, minimum is 1

3th position:
distance("ab", "ab") = 0
...
minimum is 0

и так далее.

Я, конечно, могу использовать алгоритм грубой силы для решения этой задачи. Но есть ли более быстрый алгоритм?

Спасибо за помощь.