查找所有子串的编辑距离的算法

Question

给出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", "dab") = 1 (delete)
distance("ab", "dabc") = 2 (2*delete)
....
So, minimum is 1

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

等等.

当然,我可以使用强力算法来解决这个任务.但是有更快的算法吗？

感谢帮助.

Answer 1

在给定字符串中查找子字符串非常容易。您可以使用普通的Levenshtein算法并对其进行一些修改。

首先：不要用0,1,2,3,4,5，...填充矩阵的第一行，而是完全用零填充。（绿色矩形）

第二： 然后运行算法。

第三：您 无需搜索最后一行的最后一个单元格，而是搜索最后一行中的最小值并返回它。（红色矩形）

例如： needle：“ aba”，干草堆：“ c abba c”->结果= 1（转换abba-> aba）

我对其进行了测试，并且可以正常工作。

这比您在问题中按照字符串逐个字符的建议要快得多。您只需创建一次矩阵。

Answer 2

Wagner-Fischer 算法“免费”为您提供所有前缀的答案。

http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

sWagner-Fischer 矩阵的最后一行包含to的每个前缀的编辑距离t。

因此，作为解决问题的第一步，对于每个i，运行 Wagner-Fischer 并选择最后一行中的最小元素。

我很想知道是否有其他人知道（或能找到）更好的方法。