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

Question

给定 2 个字符串 s 和 t。我需要为 s 中的每个子字符串找到到 t 的编辑距离(Levenshtein 距离)。实际上，对于 s 中的每个 i 位置，我需要知道从位置 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", haystack: "c abba c"--> 结果 = 1(转换 abba -> aba)

我测试了它，它有效。

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