Даны 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
и так далее.
Конечно, я могу использовать алгоритм грубой силы для решения этой задачи. Но есть ли более быстрый алгоритм?
Спасибо за помощь.
{2,1,**0,2**,2}неверен, потому что соседние числа могут отличаться не более чем на 1: если есть подстрокаs[i..j]с минимальным расстоянием редактирования отkдоt, то подстрокаs[(i+1)..j]может соответствоватьtсо стоимостью не болееk+1путем первого редактирования операция вставкаs[i]в самом начале строки. В вашем примере для 4-й позицииdistance("ab", "b") = 1(1 вставка) и для 5-й позицииdistance("ab", "cb") = 1(1 подстановка). - person j_random_hacker schedule 16.11.2011