Lowden

now

字符串编辑距离(动态规划求解)

动态规划求解

首先为了避免重复计算子问题,添加两个辅助数组。

.保存子问题结果。

M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) s2(0->j) 的编辑距离

.保存字符之间的编辑距离.

E[ |s1|, |s2| ] , 其中 E[ i, j ] = s[i] = s[j] ? 0 : 1

.新的计算表达式

根据性质1得到

M[ 0,0] = 0;

M[ s1i, 0 ] = |s1i|;

M[ 0, s2j ] = |s2j|;

根据性质2得到

M[ i, j ] = min(m[i-1,j-1] + E[ i, j ] , m[i, j-1] , m[i-1, j]);

复杂度

  从新的计算式看出,计算过程为

            i=1 -> |s1|

                     j=1 -> |s2|

                            M[i][j] = ……

因此复杂度为 O( |s1| * |s2| ) ,如果假设他们的长度都为n,则复杂度为 O(n^2)

posted on 2010-11-18 16:46 Lowden 阅读(379) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。
网站导航:

My Links

Blog Stats

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

好友链接

搜索

最新评论

阅读排行榜

评论排行榜