相关疑难解决方法(0)

给出2个字符串s和t.我需要找到s编辑距离(Levenshtein距离)中的每个子串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", …