求编辑距离,用动态规划解

没人知道么?
给个算法也行...

算法书上到处都有的东西，帖个伪码自己改改吧。

m[0][0] = 0;
for (i=1; i<length(s1); i++) m[i][0] = i;
for (j=1; j<length(s2); j++) m[0][j] = j;

for (i=0; i<length(s1); i++)
for (j=0; j<length(s2); j++) {
val = (s1[i] == s2[j]) ? 0 : 1;
m[i][j] = min( m[i-1][j-1] + val,
min(m[i-1][j]+1 , m[i][j-1]+1));
}

懒得认真回复。直接拷贝我的笔记给你看了。

Levenshtein Distance
来文史特距离

LD也叫edit distance，它用来表示2个字符串的相似度，不同于Hamming Distance，它可以用来比较2个长度不同的字符串。LD定义为需要最少多少步基本操作才能让2个字符串相等，基本操作包含3个：
1，插入；
2，删除；
3，替换；
比如，kiteen和sitting之间的距离可以这么计算：
1，kitten -- > sitten, 替换k为s；
2，sitten -- > sittin, 替换e为i;
3，sittin -- > sitting, 增加g；
所以，其LD为3；
计算LD的算法表示为：
int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
// d is a table with lenStr1+1 rows and lenStr2+1 columns
declare int d[0..lenStr1, 0..lenStr2]
// i and j are used to iterate over str1 and str2
declare int i, j, cost

for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j

for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j ] + 1, // deletion
d[i , j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
)

return d[lenStr1, lenStr2]；
这个算法其实就是一个矩阵的计算：
k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
首先给定第一行和第一列，然后，每个值d[i,j]这样计算：d[i,j] = min(d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+(str1[i] == str2[j]?0:1));
最后一行，最后一列的那个值就是LD的结果。
LD(str1,str2) <= max(str1.len,str2.len)；

有人提出了Levenshtein automaton（Levenshtein自动机）来计算和某个字符串距离小于某个值的集合。这样能够加快近似字符串的计算过程。见文献：Klaus U. Schulz, Stoyan Mihov, Fast String Correction with Levenshtein-Automata. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.

A Guided Tour to Approximate String Matching
GONZALO NAVARRO
这篇文章里面对这个方面（字符串相似）进行了很多描述。其中，包含了动态规划法计算Edit distance的方法。